M.A.T.R.I.X

Appearance

Volume ITechnology

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 Plain-English Breakdown ​

You are given two numbers, but instead of standard variables, their digits are stored in linked lists in reverse order. The number 342 is stored as 2 → 4 → 3. You must add the two numbers and return the result in the exact same reversed linked list format.

Constraints to note:

  • The lists can have up to 100 nodes. That means the numbers can have up to 100 digits! This is a massive hint that standard integer addition will overflow in many languages.
  • No leading zeroes (except the number 0 itself).

Brute Force Analysis ​

The trap is trying to convert the lists into standard integers, adding them, and converting them back.

  1. Traverse l1, extract digits, build string, convert to integer num1.
  2. Do the same for l2 to get num2.
  3. sum = num1 + num2.
  4. Convert sum to a string, reverse it, and build a new linked list.
  • Why it fails: While Python handles arbitrarily large integers, languages like Java, C++, or TypeScript will overflow standard 64-bit integers long before reaching 100 digits. The interviewer wants to see you implement the logic of a Full Adder (digit-by-digit addition with a carry), not rely on standard library type conversions.

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
ts
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.

ELI5 Analogy: Think back to elementary school when you learned column addition. You write two numbers on top of each other, right-aligned. You add the rightmost column. If it's 10 or more, you write down the last digit and carry the 1 to the next column left. Because our linked lists are reversed, the "rightmost column" (the ones place) is conveniently at the head of both lists. We just walk down the lists simultaneously, doing exactly what we did in elementary school.

Code Walkthrough ​

  1. Initialization: We create a dummy node to anchor the start of our result list, and a tail pointer to keep track of the end of the result list as it grows. We also initialize a carry variable to 0.
  2. The Mega-Loop: We loop as long as l1 has nodes, OR l2 has nodes, OR there is a carry left over. This beautifully handles differing lengths and a lingering final carry.
  3. The Column Sum: We initialize total with our carry. If l1 exists, we add its value to total and advance l1. We do the same for l2.
  4. The Split: Now we have a total between 0 and 19. We use divmod(total, 10) to split this into the new carry (the tens place, 0 or 1) and the digit (the ones place, 0-9). In languages without divmod, this is carry = total / 10 and digit = total % 10.
  5. Appending: We create a new ListNode with digit and attach it to our tail.next. Then we advance the tail.
  6. Return: Once everything is exhausted, our answer starts at dummy.next.

Trace ​

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

stepl1l2carry intotaldigitcarry out
19101001
29—11001
3——1110

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.

Derivation:

  • Time Complexity: Let N be the length of l1 and M be the length of l2. The while loop runs until both lists are exhausted and the carry is zero. It runs exactly \max(N, M) times, plus a potential extra iteration if a final carry remains. So, O(\max(N, M)) time.
  • Space Complexity: We allocate a new linked list for the result. Its length will be \max(N, M) or \max(N, M) + 1. Thus, the space is exactly O(\max(N, M)). Auxiliary space (excluding the output) is just the pointers and integer variables, which is O(1).

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.