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

该算法需要注意以下几点：

1. 两数按位相加如何处理进位值问题
2. 链表基本操作

 * 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<ListNode *> stack1;
        stack<ListNode *> stack2;
        ListNode *p1 = head1;
        ListNode *p2 = head2;
        if(!p1||!p2){
            if(p1 == NULL){
                return p1;
            }
            else{
                return p2;
            }
        }
        while(p1 != NULL){
            stack1.push(p1);
            p1 = p1->next;
        }
        while(p2 != NULL){
            stack2.push(p2);
            p2 = p2->next;
        }
        int stepforward = 0;
        ListNode *Dummy = (ListNode *)malloc(sizeof(ListNode));
        Dummy->next = NULL;
        while(!stack1.empty() && !stack2.empty()){
            ListNode *p =  (ListNode *)malloc(sizeof(ListNode));
            p->val = (stack1.top()->val+ stack2.top()->val +stepforward)%10;
            p->next = Dummy->next;
            Dummy->next = p;
            stepforward = (stack1.top()->val+ stack2.top()->val+stepforward)/10;
            stack1.pop();
            stack2.pop();
        }
        //Dummy->val = stack1.size();
        if(!stack1.empty()){
            while(!stack1.empty()){
                ListNode *p =  (ListNode *)malloc(sizeof(ListNode));
                p->val = (stack1.top()->val +stepforward)%10;
                p->next = Dummy->next;
                Dummy->next = p;
                stepforward = (stack1.top()->val+stepforward)/10;
                stack1.pop();
            }
            if(stepforward){
               ListNode *p =  (ListNode *)malloc(sizeof(ListNode));
                p->val = stepforward;
                p->next = Dummy->next;
                Dummy->next = p;
            }
        }
        else{
            while(!stack2.empty()){
                ListNode *p =  (ListNode *)malloc(sizeof(ListNode));
                p->val = (stack2.top()->val +stepforward)%10;
                p->next = Dummy->next;
                Dummy->next = p;
                stepforward = (stack2.top()->val+stepforward)/10;
                stack2.pop();
            }
            if(stepforward){
               ListNode *p =  (ListNode *)malloc(sizeof(ListNode));
                p->val = stepforward;
                p->next = Dummy->next;
                Dummy->next = p;
            }
        }
        p1 = Dummy->next;
        Dummy->next = NULL;
        delete Dummy;
        return p1;
    }
};
//                                     [4,6,0,2,6,6,3,6,3,0,7,8,0,4,1,7,0,5,6,5,2,4,9,9,1,5,1,5]
// [6,2,7,8,6,4,7,0,9,3,0,3,6,2,5,6,0,9,6,2,7,4,2,7,1,0,9,0,5,6,5,4,9,1,8,9,3,4,0,2,1,8,8,2,2,0]