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

注意个位，sum - 10。 注意进位 1，注意头插法，由于头插法是反的，所以push的时候用队列。

/**
 * 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> left_stack;
        stack<int> right_stack;

        queue<int> result;

        while(head1){
            left_stack.push(head1->val);
            head1 = head1->next;
        }

        while(head2){
            right_stack.push(head2->val);
            head2 = head2->next;
        }

        int max_length = 0;

        if(left_stack.size()>=right_stack.size()){
            max_length = left_stack.size();
        }else{
            max_length = right_stack.size();
        }
        ListNode* res = new ListNode(0);

        int add_on = 0;
        while(max_length){
            int up = 0;
            int down = 0;

            if(!left_stack.size()){
                up = 0;
            }else{
                up = left_stack.top();
                left_stack.pop();
            }

            if(!right_stack.size()){
                down = 0;
            }else{
                down = right_stack.top();
                right_stack.pop();
            }

            int sum = up+down + add_on;
            add_on = 0;

            if(sum>=10){
                result.push(sum-10) ;
                add_on = 1;

                if(max_length==1){
                    if(sum==10){
                        result.push(1);
                    }
                }

            }else{
                result.push(sum);
            }

          max_length--;
        }

        //result.push(add_on);

        while(!result.empty()){
            ListNode* node = new ListNode(result.front());
            result.pop();
            node->next = res->next;
            res->next = node;
        }

        return res->next;


    }
};