445.Add Two Numbers II

Tags: Medium Linked List

Links: https://leetcode.com/problems/add-two-numbers-ii/

---

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Follow up: What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

---

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        unordered_map<int, int> um1, um2;
        int pos = 1;
        ListNode *head1 = l1, *head2 = l2;

        while (head1) {
            um1[pos++] = head1 -> val;
            head1 = head1 -> next;
        }

        pos = 1;
        while (head2) {
            um2[pos++] = head2 -> val;
            head2 = head2 -> next;
        }

        int len1 = um1.size(), len2 = um2.size();
        int extra = 0;
        unordered_map<int, int> res;
        pos = 1;
        while (len1 >= 1 && len2 >= 1) {
            int tmp = um1[len1] + um2[len2] + extra;
            extra = tmp / 10;
            res[pos++] = tmp % 10;
            --len1; --len2;
        }
        if (len1) {
            while (len1 >= 1) {
                int tmp = um1[len1] + extra;
                extra = tmp / 10;
                res[pos++] = tmp % 10;
                --len1;
            }
        }
        if (len2) {
            while (len2 >= 1) {
                int tmp = um2[len2] + extra;
                extra = tmp / 10;
                res[pos++] = tmp % 10;
                --len2;
            }
        }
        if (extra) res[pos] = extra;
        else pos--;

        ListNode *dummy = new ListNode(-1);
        ListNode *p = dummy;
        while (pos >= 1) {
            ListNode *node = new ListNode(res[pos--]);
            p -> next = node;
            p = p -> next;
        }

        return dummy -> next;
    }
};

既然不允许修改链表，那么就用一个计数器去记录节点的位置。

上面的做法新建了一个链表返回，略微有点复杂，可以考虑不新建链表，而是在原来链表的最长链表上修改。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        unordered_map<int, int> um1, um2;
        int pos = 1;
        ListNode *head1 = l1, *head2 = l2;

        while (head1) {
            um1[pos++] = head1 -> val;
            head1 = head1 -> next;
        }

        pos = 1;
        while (head2) {
            um2[pos++] = head2 -> val;
            head2 = head2 -> next;
        }

        int len1 = um1.size(), len2 = um2.size();
        int extra = 0;
        unordered_map<int, int> res;
        pos = 1;
        while (len1 >= 1 && len2 >= 1) {
            int tmp = um1[len1] + um2[len2] + extra;
            extra = tmp / 10;
            res[pos++] = tmp % 10;
            --len1; --len2;
        }
        if (len1) {
            while (len1 >= 1) {
                int tmp = um1[len1] + extra;
                extra = tmp / 10;
                res[pos++] = tmp % 10;
                --len1;
            }
        }
        if (len2) {
            while (len2 >= 1) {
                int tmp = um2[len2] + extra;
                extra = tmp / 10;
                res[pos++] = tmp % 10;
                --len2;
            }
        }
        if (extra) res[pos] = extra;
        else pos--;

        ListNode *dummy = new ListNode(-1);
        ListNode *p = dummy;
        len1 = um1.size(); len2 = um2.size();
        if (len1 >= len2) {
            if (pos > len1) {
                ListNode *node = new ListNode(res[pos--]);
                p -> next = node;
                p = p -> next;
            }
            p -> next = l1;
            p = p -> next;
            while (p) {
                p -> val = res[pos--];
                p = p -> next;
            }
        }
        else {
            if (pos > len2) {
                ListNode *node = new ListNode(res[pos--]);
                p -> next = node;
                p = p -> next;
            }
            p -> next = l2;
            p = p -> next;
            while (p) {
                p -> val = res[pos--];
                p = p -> next;
            }
        }

        return dummy -> next;
    }
};