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

/**
这道题目的一般流程是先小位对齐，然后按位相加。
我这里使用了栈结构对齐，也可以反转链表对齐。
接着按位相加要注意进位符，本代码使用了temp当作进位符。
 */
#include <deque>
class Solution {
public:
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        deque<int> help1, help2;
        while(head1 != NULL){
            help1.push_back(head1->val);
            head1 = head1->next;
        }
        while(head2 != NULL){
            help2.push_back(head2->val);
            head2 = head2->next;
        }
        ListNode* ans = new ListNode(0);
        ListNode* index = NULL;
        int temp = 0;
        while(!help1.empty() && !help2.empty()){
            index = new ListNode((help1.back() + help2.back() + temp) % 10);
            index->next = ans->next;
            ans->next = index;
            temp = help1.back() + help2.back() + temp >= 10 ? 1 : 0;
            help1.pop_back();help2.pop_back();
        }
        while(!help1.empty()){
            index = new ListNode((help1.back() + temp) % 10);
            index->next = ans->next;
            ans->next = index;
            temp = help1.back() + temp >=10 ? 1 : 0;
            help1.pop_back();
        }
        while(!help2.empty()){
            index = new ListNode((help2.back() + temp) % 10);
            index->next = ans->next;
            ans->next = index;
            temp = help2.back() + temp >=10 ? 1 : 0;
            help2.pop_back();
        }
        if(temp == 1){
            index = new ListNode(1);
            index->next = ans->next;
            ans->next = index;
        }
        index = ans;
        ans = ans->next;
        delete index;
        return ans;
    }
};