题解 | #两个链表生成相加链表#

/**
 * 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, s3;
        vector<int> vec;
        ListNode* temp1=head1, *temp2=head2, *ans, *cur, *pre;
        int carray=0;
        ans = new ListNode(0);
        cur = ans;
        while(temp1){
            s1.push(temp1->val);
            temp1 = temp1->next;
        }
        while(temp2){
            s2.push(temp2->val);
            temp2 = temp2->next;
        }
        int sz1 = s1.size(), sz2 = s2.size();
        
        int i=0, j=0;
        for(; i<sz1&&j<sz2; i++, j++){
            int temp = s1.top()+s2.top() + carray;
            carray = temp>=10?1:0;
            vec.push_back(temp%10);
            s1.pop(); s2.pop();
        }
        
        int max = sz1>sz2? sz1:sz2;
        int max_idx = i>j?i:j;
        stack<int> &max_stack = sz1>sz2? s1:s2;
        
        for(; max_idx<max; max_idx++){
            int temp = max_stack.top() + carray;
            carray = temp>=10?1:0;
            vec.push_back(temp%10);
            max_stack.pop();
        }
        
        if(carray) vec.push_back(carray);
        int size = vec.size();
        ans = new ListNode(vec.back());
        vec.pop_back();
        cur = ans;
        
        for(auto iter = 1; iter<size; iter++){
            ListNode *temp = new ListNode(vec.back());
            vec.pop_back();
            cur->next = temp;
            cur = cur->next;
        }
        
        return ans;
        
    }
};