使用辅助栈来解决（其中的pre的用处理解很重要）

方法：使用栈

1. 把两个链表压入到栈1和栈2；
2. 栈的最上面元素依次相加，并压入到另一个栈3；
3. 如果栈1见底了，那么保证边界（最后的pre等于1）的同时把栈2剩下的全送到栈3；如果栈2见底则同理。
4. 把栈3中的元素全打入新链表（过程是通过链表指针 l 的指针 pNode ）。

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        stack<int> stack1, stack2, stack3;

        ListNode* l1 = head1, * l2 = head2;
        ListNode* l = nullptr;
        ListNode** pNode = &l;

        int pre = 0;

        while(l1 != nullptr)
        {
            stack1.push(l1->val);
            l1 = l1->next;
        }
        while(l2 != nullptr)
        {
            stack2.push(l2->val);
            l2 = l2->next;
        }

        while (!stack1.empty() && !stack2.empty())
        {
            stack3.push((stack1.top() + stack2.top() + pre) % 10);
            pre = (stack1.top() + stack2.top() + pre) / 10;
            stack1.pop();
            stack2.pop();
        }


        // 如果stack2空了
        if (stack2.empty())
        {
            while(!stack1.empty())
            {
                stack3.push((stack1.top() + pre) % 10);
                pre = (stack1.top() + pre) / 10;
                stack1.pop();
            }

            if (pre == 1)
            {
                stack3.push(pre);
            }
        }


        // 如果stack1空了
        if (stack1.empty())
        {
            while(!stack2.empty())
            {
                stack3.push((stack2.top() + pre) % 10);
                pre = (stack2.top() + pre) / 10;
                stack2.pop();
            }

            if (pre == 1)
            {
                stack3.push(pre);
            }
        }

        while(!stack3.empty())
        {
            *pNode = new ListNode(stack3.top());
            pNode = &((*pNode)->next);
            stack3.pop();
        }

        return l;
    }
};