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

/**
 * 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
        ListNode* res = new ListNode(-1);
        vector<int> ans1; // ans存储两个链表的数值
        vector<int> ans2;
        // 1. 先将head1和head2的数值存入ans1和ans2中
        while(head1) {
            ans1.push_back(head1->val);
            head1 = head1->next;
        }
        while(head2) {
            ans2.push_back(head2->val);
            head2 = head2->next;
        }
        // 2. 然后从数组后面遍历,将两个数相加，并根据所获得的数值创建一个链表节点头插如res链表中
        bool flag = false; // 是否存在进位
        while(ans1.size() && ans2.size()) {
            int n = ans1.size()-1;
            int m = ans2.size()-1;
            int x = ans1[n] + ans2[m] + flag;
            ans1.pop_back();
            ans2.pop_back();
            if(x >= 10) 
                flag = true;
            else
                flag = false;
            x = x % 10;
            auto node = new ListNode(x);
            node->next = res->next;
            res->next = node;
        }
        while(ans1.size()) {
            int n = ans1.size()-1;
            int x = ans1[n] + flag;
            ans1.pop_back();
            if(x >= 10) 
                flag = true;
            else
                flag = false;
            x = x % 10;
            auto node = new ListNode(x);
            node->next = res->next;
            res->next = node;
        }
        while(ans2.size()) {
            int n = ans2.size()-1;
            int x = ans2[n] + flag;
            ans2.pop_back();
            if(x >= 10) 
                flag = true;
            else
                flag = false;
            x = x % 10;
            auto node = new ListNode(x);
            node->next = res->next;
            res->next = node;
        }
        return res->next;
    }
};