题解 | #链表相加(二)#

栈

用两个栈分别存两个链表的结点，每次计算两个栈顶结点的相加值，用tmp表示进位，新建一个结点，值为除进位外的值，头插法创建新的结点。

C++代码：

class Solution {
public:
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        ListNode *head = NULL;
        stack<ListNode *> st1, st2;
        while (head1) {
            st1.push(head1);
            head1 = head1->next;
        }
        while (head2) {
            st2.push(head2);
            head2 = head2->next;
        }
        int tmp = 0;
        while (!st1.empty() || !st2.empty()) {
            int val = tmp;
            if (!st1.empty()) {
                val += st1.top()->val;
                st1.pop();
            }
            if (!st2.empty()) {
                val += st2.top()->val;
                st2.pop();
            }
            ListNode *p = new ListNode(val % 10);
            p->next = head;
            head = p;
            tmp = val / 10;
        }
        if (tmp) {
            ListNode *p = new ListNode(tmp);
            p->next = head;
            head = p;
        }
        return head;
    }
};