给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

可以假设除了数字 0 之外，这两个数字都不会以零开头。

 

示例1：

输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]

示例2：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]

示例3：

输入：l1 = [0], l2 = [0]
输出：[0]

 

提示：

    链表的长度范围为 [1, 100]
    0 <= node.val <= 9
    输入数据保证链表代表的数字无前导 0

 

进阶：如果输入链表不能修改该如何处理？换句话说，不能对列表中的节点进行翻转。

解析：

　　不进行翻转，就用个stack

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<int> a, b;
        ListNode* p = l1, *q = l2;
        ListNode* ret = nullptr;
        while(p)
        {
            a.push(p->val);
            p = p->next;
        }
        while(q)
        {
            b.push(q->val);
            q = q->next;
        }
        int d = 0;
        while(!a.empty() && !b.empty())
        {
            d = a.top() + b.top() + d;
            a.pop(); b.pop();
            ListNode* temp = new ListNode(d % 10);
            temp->next = ret;
            ret = temp;
            d /= 10;
        }
        while(!a.empty())
        {
            d = a.top() + d;
            a.pop();
            ListNode* temp = new ListNode(d % 10);
            temp->next = ret;
            ret = temp;
            d /= 10;
        }
        while(!b.empty())
        {
            d = b.top() + d;
            b.pop();
            ListNode* temp = new ListNode(d % 10);
            temp->next = ret;
            ret = temp;
            d /= 10;
        }
        if(d != 0)
        {
            ListNode* temp = new ListNode(d);
            temp->next = ret;
            ret = temp;
            d /= 10;
        }

        return ret;


    }
};