Reference: LeetCode
Difficulty: Medium

Problem

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order 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
3
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Analysis

The carry must be either $0$ or $1$ because the largest possible sum of two digits is $9 + 9 + 1 = 19$.

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]

Simulation (Iteration)

Simulate digits-by-digits sum starting from the left.

Note:

  • Use dummy head node of the returning list. Return dummy‘s next.
  • Learn how to write better code of setting next (with null case).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
  ListNode dummy = new ListNode(-1);
  ListNode prev = dummy;
  int carry = 0;
  while (l1 != null || l2 != null || carry > 0) {
    int x = (l1 != null) ? l1.val : 0;
    int y = (l2 != null) ? l2.val : 0;
    int sum = x + y + carry;
    prev.next = new ListNode(sum % 10);
    carry = sum / 10;
    // set next
    prev = prev.next;
    if (l1 != null) l1 = l1.next;
    if (l2 != null) l2 = l2.next; // Bad code: l1 = (l1 != null) ? l1.next : null;
  }
  return dummy.next;
}

Time: $O(\text{max}(M, N))$
Space: $O(\text{max}(M, N))$

Simulation (Recursion)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
  return add(l1, l2, 0);
}

private ListNode add(ListNode l1, ListNode l2, int carry) {
  if (l1 == null && l2 == null && carry <= 0) { // base case
    // 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 ret = new ListNode(sum % 10);
  // set next
  if (l1 != null) l1 = l1.next;
  if (l2 != null) l2 = l2.next;
  ret.next = add(l1, l2, sum / 10);
  return ret;
}

Time: $O(\text{max}(M, N))$
Space: $O(\text{max}(M, N))$ including the call stack.

Conversion

Instead of dealing with all the edge cases, just convert the linked lists to integers and convert the sum to a linked list.

Time: $O(\max(M, N))$
Space: $O(\max(M, N))$