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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
#include <vector>
class Solution {
  private:
    int greaterLen = 0;
    vector<ListNode*> vecList1;
    vector<ListNode*> vecList2;
    vector<ListNode*> vecList3;
  public:
    /**
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        int head1Len = 0;
        int head2Len = 0;
        ListNode* headList1 = head1;
        ListNode* headList2 = head2;
        while (head1 || head2) {
            if (head1) {
                head1Len++;
                head1 = head1->next;
            }
            if (head2) {
                head2Len++;
                head2 = head2->next;
            }
        }
        greaterLen = (head1Len >= head2Len) ? head1Len : head2Len;
        vecList1.resize(greaterLen + 1);
        vecList2.resize(greaterLen + 1);
        vecList3.resize(greaterLen + 1);
        ListNode* headNULL1 = new ListNode(0);
        int diffLen = 0;
        if (head1Len > head2Len) {
            diffLen = head1Len - head2Len;
            for (int i = 0; i <= greaterLen - 1; i++) {
                if (i < diffLen) {
                    vecList2[i] = headNULL1;
                    //vecList2[i]->val = 0;
                    if (i == diffLen - 1) {
                        vecList2[i + 1] = headList2;
                        vecList2[i]->next = vecList2[i + 1];
                        headList2 = headList2->next;
                    } else {
                        ListNode* headNULL2 = new ListNode(0);
                        vecList2[i]->next = headNULL2;
                    }
                } else {
                    if (i != diffLen) {
                        vecList2[i] = headList2;
                        headList2 = headList2->next;
                    }
                }
                vecList1[i] = headList1;
                vecList3[i] = headList1;
                headList1 = headList1->next;
            }
        } else if (head1Len < head2Len) {
            diffLen = head2Len - head1Len;
            for (int i = 0; i <= greaterLen - 1; i++) {
                if (i < diffLen) {
                    vecList1[i] = headNULL1;
                    if (i == diffLen - 1) {
                        vecList1[i + 1] = headList1;
                        vecList1[i]->next = vecList1[i + 1];
                        headList1 = headList1->next;
                    } else {
                        ListNode* headNULL2 = new ListNode(0);
                        vecList1[i]->next = headNULL2;
                    }
                } else {
                    if (i != diffLen) {
                        vecList1[i] = headList1;
                        headList1 = headList1->next;
                    }
                }
                vecList2[i] = headList2;
                vecList3[i] = headList2;
                headList2 = headList2->next;
            }
        } else {
            for (int i = 0; i <= greaterLen - 1; i++) {
                vecList1[i] = headList1;
                vecList2[i] = headList2;
                vecList3[i] = headList1;
                headList1 = headList1->next;
                headList2 = headList2->next;
            }
        }
        int digit = 0;
        int tempValue = 0;
        for (int i = greaterLen - 1; i >= 0; i--) {
            tempValue = vecList1[i]->val + vecList2[i]->val;
            if (i < greaterLen - 1) {
                tempValue = vecList1[i]->val + vecList2[i]->val + digit;
            }
            if (tempValue >= 10) {
                vecList3[i]->val = tempValue % 10;
                if (i == 0) {
                    ListNode* headNULL3 = new ListNode(1);
                    vecList3.insert(vecList3.begin(), headNULL3);
                    vecList3[0]->next = vecList3[1];
                }
                digit = 1;
            } else {
                vecList3[i]->val = tempValue;
                digit = 0;
            }
        }
        return vecList3[0];
    }
};