Reference: LeetCode
Difficulty: Medium

My Post: Java Solution Using Two Stacks

Problem

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.

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

Example:

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

Follow up:

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

  • Use Stack.

Analysis

I’ve tried direct recursion without reversing, but couldn’t make it work.

Test Case:

1
2
3
4
5
6
7
8
9
10
11
12
// When one list is longer than the other.
[0, 1]
[0, 1, 2]
[0, 2, 2]
// When one list is null, which means an empty list.
[]
[0, 1]
[0, 1]
// When sum could have an extra carry of one at the end, which is easy to forget.
[9, 9]
[1]
[0, 0, 1]

Reverse + Simulation

Note:

  • Remember to reverse the return node before finishing.
  • Notice the base case of reverse. Come up with some examples.
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
public ListNode reverseAndAdd(ListNode l1, ListNode l2) {
if (l1 == null || l2 == null) throw new IllegalArgumentException();
l1 = reverse(l1);
l2 = reverse(l2);
ListNode L = add(l1, l2, 0);
L = reverse(L);
return L;
// or return reverse(add(reverse(l1), reverse(l2), 0));
}

// 1 - 2 - 3 - 4
// 1 - 4 - 3 - 2
// x head x.next
private ListNode reverse(ListNode x) {
if (x == null || x.next == null) return x; // find new head
ListNode head = reverse(x.next);
x.next.next = x;
x.next = null;
return head;
}

private ListNode add(ListNode l1, ListNode l2, int carry) {
if (l1 == null && l2 == null && carry <= 0) {
// if (carry > 0) return new ListNode(carry);
// else return null;
return null;
}
int x = (l1 == null) ? 0 : l1.val;
int y = (l2 == null) ? 0 : l2.val;
int sum = x + y + carry;
ListNode newNode = new ListNode(sum % 10);
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
newNode.next = add(l1, l2, sum / 10);
return newNode;
}

Time: $O(M + N)$ 2 ms
Space: $O(M + N)$

Use Two Stacks

Use two stacks to simulate the add operation

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
// Use Two Stacks
public ListNode useTwoStacks(ListNode l1, ListNode l2) {
if (l1 == null || l2 == null) throw new IllegalArgumentException();
Stack<ListNode> s1 = new Stack<>();
Stack<ListNode> s2 = new Stack<>();
while (l1 != null) {
s1.push(l1);
l1 = l1.next;
}
while (l2 != null) {
s2.push(l2);
l2 = l2.next;
}
return addTwoStacks(s1, s2);
}

private ListNode addTwoStacks(Stack<ListNode> s1, Stack<ListNode> s2) {
if (s1 == null) s1 = new Stack<>();
if (s2 == null) s2 = new Stack<>();

ListNode dummy = new ListNode(-1);
int carry = 0;
while (!s1.isEmpty() || !s2.isEmpty() || carry > 0) {
int x = s1.isEmpty() ? 0 : s1.pop().val;
int y = s2.isEmpty() ? 0 : s2.pop().val;
int sum = x + y + carry;
carry = sum / 10;
ListNode newNode = new ListNode(sum % 10);
newNode.next = dummy.next;
dummy.next = newNode; // addFirst
}
return dummy.next;
}

Time: $O(M + N)$ 6 ms
Space: $O(M + N)$