Add Two Numbers by Two Linked List (most significant digit comes first)

ou 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

Mathematically, we need to add the digits from the least significant (right) to most significant (left). As the linked lists are both in the reversed order – we can reverse the linked lists and start adding digits and carry over. Alternatively, we can convert the linked lists first to numbers, add two numbers, and convert the result back to the linked list. Also, we can push the numbers to two stacks, then popping out yields the digits in the correct order (from least to most significant).

Reversing the Linked List

Reverse the linked lists then we can start adding digits as they appear in the linked lists. But this require we modify the linked lists.

Transforming Linked List to Numbers/Strings

Converting linked lists to numbers would do the trick. However, the numbers may overflow. One workaround is to convert linked lists to strings.

Pushing the Numbers into Stack

The best solution is to use two stacks, then we need to follow the linked list and push each digit to the stack. Then when we pop out the digits one by one, we are essentially traversing the digits from right to the left – then we need to add two digits and carry over. Remember to carry over the last digit as we might need to allocate a node for it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

/**
 * 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) {
        stack<int> st1, st2;
        while (l1) {
            st1.push(l1->val);
            l1 = l1->next;
        }
        while (l2) {
            st2.push(l2->val);
            l2 = l2->next;
        }
        ListNode* prev = NULL;
        int c = 0;
        while (!st1.empty() || (!st2.empty())) {
            int sum = c;
            if (!st1.empty()) {
                sum += st1.top();
                st1.pop();
            }
            if (!st2.empty()) {
                sum += st2.top();
                st2.pop();
            }
            c = sum / 10;
            ListNode* n = new ListNode(sum % 10);
            n->next = prev;
            prev = n;
        }
        if (c > 0) {
            ListNode* n = new ListNode(c);
            n->next = prev;
            prev = n;
        }
        return prev;
    }
};

/**
 * 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) {
        stack<int> st1, st2;
        while (l1) {
            st1.push(l1->val);
            l1 = l1->next;
        }
        while (l2) {
            st2.push(l2->val);
            l2 = l2->next;
        }
        ListNode* prev = NULL;
        int c = 0;
        while (!st1.empty() || (!st2.empty())) {
            int sum = c;
            if (!st1.empty()) {
                sum += st1.top();
                st1.pop();
            }
            if (!st2.empty()) {
                sum += st2.top();
                st2.pop();
            }
            c = sum / 10;
            ListNode* n = new ListNode(sum % 10);
            n->next = prev;
            prev = n;
        }
        if (c > 0) {
            ListNode* n = new ListNode(c);
            n->next = prev;
            prev = n;
        }
        return prev;
    }
};

During adding two digits, we allocate a new node and link to its previous one – which will be returned as head in the end. The space complexity is O(N) and the time complexity is also O(N) where N is the number of nodes in the longest linked list.

–EOF (The Ultimate Computing & Technology Blog) —