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)$