Problem description:
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:

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

Solution:
This question is a followup from “2. Add two number.” The different part is that the significant digit comes first. However, we need to start from least significant digit when we do calculation. Even though the question states that you can not modify the input list, we can use a stack, first in last out, to achieve the reverse order calculation.

Space: O(n)

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
/**
 * 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> s1, s2;
        while(l1 != NULL){
            s1.push(l1->val);
            l1= l1->next;
        }
        while(l2 != NULL){
            s2.push(l2->val);
            l2= l2->next;
        }
        
        int sum= 0;
        ListNode* list= new ListNode(0);
        while (!s1.empty() ||!s2.empty()){
            if(!s1.empty()) {
                sum += s1.top();
                s1.pop();
            }
            if(!s2.empty()){
                sum += s2.top();  
                s2.pop();
            } 
            
            list->val = sum %10;
            ListNode* head = new ListNode(sum/10);
            head->next = list;
            list = head;
            sum/=10;
        }
        return list->val ==0 ? list->next: list;
    }
};

Second time:
Thought process: we need to start calculation from the last node. More specifically, we need to calculate backward, and Stack is a good way to do so. 

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
46
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<ListNode> stk1 = new Stack();
        Stack<ListNode> stk2 = new Stack();
        while(l1 != null){
            stk1.push(l1);
            l1 = l1.next;
        }
        while(l2 != null){
            stk2.push(l2);
            l2 = l2.next;
        }
        
        ListNode dummy = new ListNode(0);
        ListNode head = dummy;
        int carry = 0;
        while(stk1.size() != 0 || stk2.size() != 0 || carry != 0){
            ListNode newNode = new ListNode(carry);
            if(!stk1.empty()){
                newNode.val += stk1.pop().val;
            }
            if(!stk2.empty()){
                newNode.val += stk2.pop().val;
            }
            
            carry = newNode.val/10;
            newNode.val %= 10;
            ListNode tmp = head.next;
            newNode.next = tmp;
            head.next = newNode;
            
        }
        
        return dummy.next;
    }
}

we can simplify the code to this

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<ListNode> stk1 = new Stack();
        Stack<ListNode> stk2 = new Stack();
        while(l1 != null){
            stk1.push(l1);
            l1 = l1.next;
        }
        while(l2 != null){
            stk2.push(l2);
            l2 = l2.next;
        }
        
        ListNode list = null; //represents the first node of result list, init is null
        int carry = 0;
        while(stk1.size() != 0 || stk2.size() != 0 || carry != 0){
            
            if(!stk1.empty()) carry += stk1.pop().val;
            if(!stk2.empty()) carry += stk2.pop().val;
            
            ListNode newHead = new ListNode(carry%10);
            newHead.next = list; 
            list = newHead;
            carry /= 10;
        }
        
        return list;
    }
}

time complexity: $O(n)$
space complexity: $O(n)$
reference:

related question:
2. Add Two Numbers