Add Two Numbers

Table of contents

1. Problem
2. Solution
   1. Simultaneous traversal
   2. Which linked list is longer?
   3. Leftover carry

---

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 contains a single digit. Add the two numbers and return the sum as a linked list.

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

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

---

Solution

So basically the number 123 is represented as a linked list 3 -> 2 -> 1, and the number 456 is represented as a linked list 6 -> 5 -> 4.

The answer should be 579, which is represented as a linked list 9 -> 7 -> 5.

Things to note:

• The two linked lists may not have the same length.
• We don’t know the length of the linked lists.
• The answer may have at most one more digit than the longer linked list (because of the carry).

The code consists of three parts:

1. Traverse the two linked lists simultaneously and add the corresponding digits.
2. Check which linked list is longer.
3. If there is a carry, we need to do leftover work on the longer linked list.

Simultaneous traversal

We do not create a separate linked list for the answer. The answer is stored in-place in both linked lists.

// Keep track of the head of both linked lists.
ListNode ans1 = l1;
ListNode ans2 = l2;
// Why both?
// Because we don't know which one is longer,
// and we want to use the longer one for the answer.

// Keep track of the previous node of both linked lists.
ListNode l1_prev = null;
ListNode l2_prev = null;
// Why? In case we need to add a new node to the end of the linked list.

int carry = 0;

// Go on until one of the linked lists is exhausted.
while (l1 != null && l2 != null) {
  int sum = l1.val + l2.val + carry;
  carry = sum / 10; // Save for later

  // In-place update on both
  l1.val = sum % 10;
  l2.val = sum % 10;

  l1_prev = l1;
  l2_prev = l2;
  l1 = l1.next;
  l2 = l2.next;
}

Which linked list is longer?

Now that we’re out of the loop, either l1 or l2, or both, is null.

// Tracking candidates for leftover work
ListNode ans;  // Head to return for the answer
ListNode prev;  // In case carry requires new node
ListNode curr;  // Where to start leftover work

if (l1 != null) {
  ans = ans1;
  prev = l1_prev;
  curr = l1;
} else {
  ans = ans2;
  prev = l2_prev;
  curr = l2;
}

Leftover carry

// Carry could go on until the end of the longer list
while (carry > 0) {
  // If we're at the end of the longer list,
  if (curr == null) {
    // This is why we had to keep track of the previous node
    prev.next = new ListNode(1);
    break;
  }

  // Same thing as before, just with one linked list
  int sum = curr.val + carry;
  carry = sum / 10;
  curr.val = sum % 10;

  prev = curr;
  curr = curr.next;
}

// Return the head of the answer
return ans;

Complexity is $O(n)$ where $n$ is the length of the longer linked list.