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

因为本题是链表从后往前相加，为逆序，可以考虑栈

 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        stack<int>s1,s2;
        while(head1){
            s1.push(head1->val);
            head1 = head1->next;
        }
        while(head2){
            s2.push(head2->val);
            head2 = head2->next;
        }
        
        int carry = 0;
        ListNode* ans = nullptr;
        while(!s1.empty() or !s2.empty() or carry!=0){
            int a = s1.empty() ? 0 : s1.top();
            int b = s2.empty() ? 0 : s2.top();
            
            if(!s1.empty())
                s1.pop();
            if(!s2.empty())
                s2.pop();
            
            int cur = a + b + carry;
            carry = cur/10;
            cur = cur%10;
            auto p = new ListNode(cur);
            p->next = ans;
            ans = p;
        }
        return ans;
    }
};