Add Two Numbers

The problem

You are given l1 and l2, the first nodes of two linked lists. Each list stores a whole number, zero or greater, one digit per node, starting with the ones digit: 2 → 4 → 3 stores 342. Add the two numbers and return the first node of a list that stores the sum the same way. Each list has at least one node, and the lists may differ in length. No number has extra zeros at its high end, so zero is the single node 0. A node holds a digit, val, and a link, next, to the node after it, and the last node's next is null.

What to write

type ListNode = {val:number;next:ListNode|null};

function solve(l1: ListNode | null, l2: ListNode | null): ListNode | null

Input
l1 = {"val":2,"next":{"val":4,"next":{"val":3,"next":null}}}
l2 = {"val":5,"next":{"val":6,"next":{"val":4,"next":null}}}

Output
{"val":7,"next":{"val":0,"next":{"val":8,"next":null}}}

Input
l1 = {"val":0,"next":null}
l2 = {"val":0,"next":null}

Output
{"val":0,"next":null}

Constraints

Each input has 1–100 nodes with digits 0–9.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Each list can hold 100 digits. Many languages cannot store a number that long exactly: a JavaScript number is exact only up to 9,007,199,254,740,991, which has 16 digits. So do not count on rebuilding the two numbers. Notice which digit each list gives you first: the ones digit.

2. Hint 2: Ask a smaller question

   Add 342 and 465 on paper, in columns. Which column do you start with? When a column adds up to 10 or more, what do you write down and what do you take to the next column?

3. Hint 3: Name the pattern

   This is the addition you learned at school: one column at a time, write the last digit of the column's total and carry the rest into the next column. Working through a number one digit at a time is digit-by-digit arithmetic. The signal: numbers that arrive as separate digits. Read the lesson on digit-by-digit arithmetic.

4. Hint 4: State the invariant

   Before each column, the answer holds the correct lower digits of the sum, and the carry holds what those columns passed on. The carry is always 0 or 1, because two digits and a carry add up to at most 9 + 9 + 1 = 19.

5. Hint 5: Sketch the pseudocode

   carry = 0, and the answer starts empty. While either list has a node or carry is not 0: total = carry plus the digit of each list that still has one, and those lists move on. Append a node holding the remainder of total divided by 10. carry = total divided by 10, rounded down. Return the answer.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Traverse both lists together, emit each sum modulo ten, and carry the remaining digit forward.

The slow way

Turn each list into a number, add the two numbers, and write the digits of the sum into a new list. That works in Python, whose whole numbers have no size limit. A JavaScript number is exact only up to 9,007,199,254,740,991, which has 16 digits. A list can hold 100 digits, so in JavaScript long sums come out with wrong digits.

The insight

The lists give you the digits in the order that column addition needs them: ones first. So you can add one pair of digits at a time and write each digit of the answer as soon as its column is added. All that passes from one column to the next is a carry of 0 or 1.

Step by step

1. Start the answer with a placeholder node and a carry of 0. A placeholder, often called a dummy node, is an extra node in front, so the first digit is appended like every other. The carry is what one column passes to the next. Nothing has been passed yet.
2. Keep going while either number has a digit or a carry is left. The lists can differ in length, so one may end before the other. After both have ended a carry can still be waiting: 99 + 1 needs a third digit.
3. Add the carry and the digits that exist, then step past them. A list that has run out adds nothing, which is the same as a digit of 0. Each digit belongs to one column, so its list moves on to the next node.
4. Split the total: the last digit is written, the rest is carried. One column holds one digit. The total is at most 9 + 9 + 1 = 19. Its last digit stays in this column. A total of 10 or more also sends a 1 to the next column.
5. Append the digit as a new node at the end of the answer. The answer is stored ones digit first as well, so each new digit comes after the digits already written. A marker on the last node of the answer shows where to append, and then moves onto the new node.
6. The sum starts at the node after the placeholder. The placeholder is not a digit of the sum. The node after the placeholder holds the ones digit. That node always exists, because each list has at least one digit.

The same numbered steps are the comments in each solution.

function solve(l1, l2) {
  // 1. Start the answer with a placeholder node and a carry of 0
  const dummy = { val: 0, next: null };
  let tail = dummy,
    carry = 0;
  // 2. Keep going while either number has a digit or a carry is left
  while (l1 || l2 || carry) {
    // 3. Add the carry and the digits that exist, then step past them
    const sum = (l1?.val ?? 0) + (l2?.val ?? 0) + carry;
    l1 = l1?.next ?? null;
    l2 = l2?.next ?? null;
    // 4. Split the total: the last digit is written, the rest is carried
    const digit = sum % 10;
    carry = Math.floor(sum / 10);
    // 5. Append the digit as a new node at the end of the answer
    tail.next = { val: digit, next: null };
    tail = tail.next;
  }
  // 6. The sum starts at the node after the placeholder
  return dummy.next;
}

type ListNode = { val: number; next: ListNode | null };
function solve(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  // 1. Start the answer with a placeholder node and a carry of 0
  const dummy: ListNode = { val: 0, next: null };
  let tail = dummy,
    carry = 0;
  // 2. Keep going while either number has a digit or a carry is left
  while (l1 || l2 || carry) {
    // 3. Add the carry and the digits that exist, then step past them
    const sum = (l1?.val ?? 0) + (l2?.val ?? 0) + carry;
    l1 = l1?.next ?? null;
    l2 = l2?.next ?? null;
    // 4. Split the total: the last digit is written, the rest is carried
    const digit = sum % 10;
    carry = Math.floor(sum / 10);
    // 5. Append the digit as a new node at the end of the answer
    tail.next = { val: digit, next: null };
    tail = tail.next;
  }
  // 6. The sum starts at the node after the placeholder
  return dummy.next;
}

def solve(l1, l2):
    # 1. Start the answer with a placeholder node and a carry of 0
    dummy = tail = ListNode()
    carry = 0
    # 2. Keep going while either number has a digit or a carry is left
    while l1 or l2 or carry:
        # 3. Add the carry and the digits that exist, then step past them
        total = carry
        if l1:
            total += l1.val
            l1 = l1.next
        if l2:
            total += l2.val
            l2 = l2.next
        # 4. Split the total: the last digit is written, the rest is carried
        digit = total % 10
        carry = total // 10
        # 5. Append the digit as a new node at the end of the answer
        tail.next = ListNode(digit)
        tail = tail.next
    # 6. The sum starts at the node after the placeholder
    return dummy.next

Example 1, traced

Input
l1 = {"val":2,"next":{"val":4,"next":{"val":3,"next":null}}}
l2 = {"val":5,"next":{"val":6,"next":{"val":4,"next":null}}}

Output
{"val":7,"next":{"val":0,"next":{"val":8,"next":null}}}

Why it works

After each round, the answer holds the correct lower digits of the sum and the carry holds what those columns passed on, as in addition on paper. The loop goes on while a digit or a carry is left, so no column is skipped and a last carry gets its own node.

Time and space

Time O(max(m,n)), extra space O(max(m,n)) including output. The loop runs once for each digit of the longer number, and at most once more for a last carry. So the time is O(max(m, n)) for lists of m and n nodes. The answer gets one node per round and nothing else grows: O(max(m, n)) space, counting the output.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Keep the carry in the loop condition. If the loop stops when both lists end, a last carry is dropped: 99 + 1 comes out as 0 → 0 instead of 0 → 0 → 1.
• Do not stop at the end of the shorter list. The other number's remaining digits still belong in the answer: 321 + 4, given as 1 → 2 → 3 and 4, would come out as the single node 5.
• Round the carry down to a whole number. With ordinary division, a total of 7 leaves a carry of 0.7, and every digit after that comes out as a fraction.

Pattern

Digit-by-digit arithmetic. Builds on Merge Two Sorted Lists.

Keep going