4.9.6 — Add Two Numbers

LeetCode 2 · Medium

The problem

Two numbers are stored as linked lists, one digit per node, least significant digit first. Add them and return the sum in the same form.

(2 → 4 → 3) + (5 → 6 → 4)   =   7 → 0 → 8
   342      +     465       =     807

The pattern

The lists are stored backwards, and that is a gift rather than an obstacle. Addition starts at the least significant digit and carries upwards — which is exactly the order the lists are already in. Walk both from the head, add, carry, done.

You do not convert the lists to integers. For long lists that overflows in most languages, and it misses the point of the problem, which is that this is how arbitrary-precision arithmetic actually works.

The solution

Python

class Solution:
    def addTwoNumbers(self, l1, l2):
        dummy = ListNode()
        tail = dummy
        carry = 0

        while l1 or l2 or carry:                   # note the carry
            total = carry
            if l1:
                total += l1.val
                l1 = l1.next
            if l2:
                total += l2.val
                l2 = l2.next

            carry, digit = divmod(total, 10)
            tail.next = ListNode(digit)
            tail = tail.next

        return dummy.next

TypeScript

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  const dummy = new ListNode();
  let tail = dummy;
  let carry = 0;

  while (l1 || l2 || carry) {
    let total = carry;
    if (l1) { total += l1.val; l1 = l1.next; }
    if (l2) { total += l2.val; l2 = l2.next; }

    carry = Math.floor(total / 10);
    tail.next = new ListNode(total % 10);
    tail = tail.next;
  }

  return dummy.next;
}

while l1 or l2 or carry is the whole problem in one line. Three conditions, and each covers a case:

• l1 or l2 — the lists may be different lengths, and the shorter one simply contributes nothing once it runs out.
• carry — this is the one people forget. (5) + (5) gives 10, both lists are exhausted, and there is still a 1 to place. Without the carry condition the answer comes out as 0 instead of 0 → 1.

Handling all three in the loop condition removes every special case. There is no separate "drain the longer list" loop and no post-loop carry check.

divmod(total, 10) returns the quotient and remainder together — the carry and the digit. Since each digit is at most 9, total is at most 9 + 9 + 1 = 19, so the carry is always 0 or 1.

The dummy head again removes the special case for the first node.

Trace

(9 → 9) + (1), which is 99 + 1 = 100.

step	l1	l2	carry in	total	digit	carry out
1	9	1	0	10	0	1
2	9	—	1	10	0	1
3	—	—	1	1	1	0

Result 0 → 0 → 1, which reads as 100. ✓ Step 3 only happens because of the or carry.

Complexity

O(\max(n, m)) time, O(\max(n, m)) space for the output — which is unavoidable, since the answer is that long.

The forward-order variant

Add Two Numbers II (LeetCode 445) stores the digits most significant first, and forbids reversing the input. Now addition has to start at the ends of the lists, which you cannot walk to.

Three ways out, and the choice is worth knowing:

• Reverse both lists, add, reverse the result. Simplest, and only allowed if you may modify the input.
• Push both lists onto stacks. Popping gives you the digits from least significant first, which is this problem again. O(n) space, no mutation.
• Compute the lengths, pad the shorter conceptually, and recurse, letting the call stack unwind from the least significant end.

The stack version is the usual answer, and it is a good illustration of using a stack purely to reverse the order of processing.

Where this goes next

• Multiply Strings — the same carry discipline in two dimensions. Chapter 4.28.
• Plus One — add 1 to a digit array, where the only interesting case is all nines. Chapter 4.28.
• Arbitrary-precision arithmetic — Python's built-in integers do exactly this internally, in base 2^{30} rather than base 10. Every "big integer" library is this loop.

The rule: digit-by-digit arithmetic is a loop over positions with a carry that must survive past the end of both inputs.

What the interviewer will push on

"What if the lists have different lengths?" The if l1 and if l2 guards handle it; the shorter list stops contributing.

"What if there is a carry at the very end?" The or carry in the loop condition. Give the (5) + (5) example.

"Why not convert to integers and add?" Overflow for long lists, and it defeats the purpose. In Python integers are unbounded so it would technically work, which makes it a good moment to say that you know the difference between what a language allows and what an algorithm should assume.

"What if the digits were stored most significant first?" The three approaches above, with stacks as the usual answer.

One thing to volunteer: point out the loop condition covers all three termination cases at once, so no cleanup code is needed. That is the design decision in this problem.

Next: 4.9.7 Linked List Cycle — two pointers at different speeds, and a proof that they must meet.