Add Two Numbers

1. Problem & Core Objective

Two non-empty lists represent non-negative integers with their digits stored in reverse order, one digit per node. Add them and return the sum as a list in the same format.

l1 = [2,4,3]   represents 342
l2 = [5,6,4]   represents 465
sum = 807   →  [7,0,8]

Constraints: 1 <= length <= 100 · 0 <= Node.val <= 9 · no leading zeros except the number 0 itself

What's actually being tested: whether you notice the reverse order is a gift, and whether you handle carry cleanly — especially the final carry, which is the bug everyone writes at least once.

2. First-Principles Thought Process

Why reverse order is a gift, not an obstacle

Grade-school addition starts at the least significant digit and carries leftward. Reverse storage puts the least significant digit at the head — exactly where a linked list lets you start.

So you walk both lists front to back, which is the only direction a singly linked list offers, and that happens to be the correct direction for addition. No reversal needed.

If the digits were stored most-significant-first, you'd have a genuine problem: you'd need to reverse both lists, or use a stack, or recurse to the end and add on the way back up. That's the follow-up in §7.

The algorithm is just column addition

    3 4 2          walk from the head:
  + 4 6 5          2+5 = 7,  carry 0
  -------          4+6 = 10, digit 0, carry 1
    8 0 7          3+4+1 = 8, carry 0

At each position: sum = d1 + d2 + carry, emit sum % 10, keep carry = sum / 10.

Since each digit is at most 9, sum is at most 9 + 9 + 1 = 19. So carry is always 0 or 1, and sum / 10 is exact integer division.

The three things that bite

1. Unequal lengths. One list runs out first. Treat the missing digits as 0 rather than writing a separate loop.
2. A final carry. [5] + [5] is [0,1] — the result is longer than either input. Forgetting this returns [0].
3. Building the output. Dummy head again, for the same reason as question 2.

3. Solution Paths

Approach 1 — Convert to a number, add, convert back (brute force)

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    long a = toNumber(l1), b = toNumber(l2);
    long sum = a + b;

    ListNode dummy = new ListNode(), tail = dummy;
    if (sum == 0) return new ListNode(0);
    while (sum > 0) { tail.next = new ListNode((int)(sum % 10)); tail = tail.next; sum /= 10; }
    return dummy.next;
}

private long toNumber(ListNode l) {
    long n = 0, place = 1;
    for (ListNode p = l; p != null; p = p.next) { n += p.val * place; place *= 10; }
    return n;
}

• Time O(n + m) · Space O(1) beyond the output

Counter-questions on this approach

⭐ "The lists can hold 100 digits. What happens to your long?"

It overflows, silently and catastrophically. A long holds about 19 digits; a 100-digit number is off by 80 orders of magnitude. The result would be arbitrary garbage with no exception thrown.

This is the fatal flaw. The lists are the number representation precisely because the values don't fit in a primitive — that's why the problem stores digits at all.

"Would BigInteger fix it?"

It would produce correct answers, yes. But it's O(n) to build the BigInteger from digits, O(n) to add, O(n) to decompose — so no asymptotic gain — and it sidesteps the entire point of the exercise, which is digit-by-digit carry handling. I'd mention it as the production answer and then write the real one.

"Why the if (sum == 0) special case?"

Because while (sum > 0) never runs for zero, returning an empty list instead of [0]. It's the same class of bug as forgetting the final carry — a loop condition that skips a legitimate case. Worth noting that the digit-by-digit version has no such problem.

Approach 2 — Digit-by-digit with carry (optimal)

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(), tail = dummy;
    int carry = 0;

    while (l1 != null || l2 != null || carry != 0) {
        int a = (l1 != null) ? l1.val : 0;          // missing digits are 0
        int b = (l2 != null) ? l2.val : 0;
        int sum = a + b + carry;

        tail.next = new ListNode(sum % 10);
        tail = tail.next;
        carry = sum / 10;

        if (l1 != null) l1 = l1.next;
        if (l2 != null) l2 = l2.next;
    }
    return dummy.next;
}

Trace — [2,4,3] + [5,6,4]:

Result [7,0,8] ✓

Trace — [9,9] + [1] (the case that catches people):

Result [0,0,1] = 100 ✓ — step 3 only happens because carry != 0 is in the loop condition.

• Time O(max(n, m)) · Space O(1) beyond the output

Counter-questions on this approach

⭐ "Why is carry != 0 in the loop condition?"

Because the result can be longer than both inputs. 99 + 1 = 100 produces three digits from two- and one-digit inputs. Without that clause the loop exits when both lists are exhausted and the final carry is dropped, giving [0,0] — the wrong answer, silently.

It's the single most common bug in this problem. The alternative is an if (carry > 0) after the loop, which works but duplicates the node-append code.

⭐ "Why treat missing digits as 0 rather than writing a second loop?"

Because 0 is the identity for addition, so a missing digit contributes nothing — the general case already handles it. Splitting into "both lists" then "whichever remains" means two loops with the same carry logic in each, and the carry logic is exactly where the bugs are. One loop, one place to get it right.

"Can carry ever be more than 1?"

No. Each digit is at most 9, so sum <= 9 + 9 + 1 = 19 and sum / 10 <= 1. That's what makes sum % 10 and sum / 10 safe as the digit and carry. If the base were larger, or if nodes held multi-digit chunks, the same code would still work — but I'd want to check the bound rather than assume it.

"Why advance the pointers with if guards instead of unconditionally?"

l1 = l1.next throws when l1 is already null. The guards are load-bearing, not defensive — with unequal lengths one pointer goes null while the loop is still running on the other.

"Does this mutate the inputs?"

No. It reads val and allocates fresh nodes for the result. That's the right choice here since the inputs represent numbers the caller may still need — unlike question 2, where splicing was explicitly wanted.

Comparison

4. Why the Optimal Wins

This isn't a speed comparison — the naive version is wrong, not slow. A 100-digit number cannot fit in any primitive, and the whole reason the problem hands you a linked list of digits is that the value exceeds machine integers.

Against BigInteger: same complexity, correct answers, but three conversions instead of one pass, and it outsources the exact mechanic being examined.

The digit-by-digit version works at any length because it never holds more than one column in a register at a time — which is precisely how hardware adders and arbitrary-precision libraries work internally.

The framing worth keeping:

When digits are stored least-significant-first, addition is a single forward pass. Put carry != 0 in the loop condition so the final carry can't be dropped.

5. Java Prerequisites

Digit and carry extraction

int digit = sum % 10;
int carry = sum / 10;      // integer division truncates — exactly what's wanted

Treating an exhausted list as zero

int a = (l1 != null) ? l1.val : 0;

Guarded advance

if (l1 != null) l1 = l1.next;

The three-clause loop condition — the shape worth memorizing:

while (l1 != null || l2 != null || carry != 0)

Two inputs and a piece of state, any of which can keep the loop alive.

Overflow reminder. int maxes near 2.1 × 10^9 (10 digits); long near 9.2 × 10^18 (19 digits). Neither is close to 100 digits. See 01.

6. Interview Communication Guide

Clarifying questions: Digits reversed, so the head is least significant (yes — confirm, it's the crux)? Can either list be longer (yes)? Any leading zeros to worry about (no, except the number 0)? Can I allocate new nodes or must I reuse (allocate)? Could the numbers be negative (no)?

The pitch

"The reverse storage is actually a gift. Addition naturally starts at the least significant digit and carries upward, and reverse order puts the least significant digit at the head — which is the only place a singly linked list lets me start. So I walk both lists forward, which is exactly the direction column addition wants. No reversal needed.

At each position I take a digit from each list — zero if that list has run out, since zero is the additive identity and the general case then covers it — add the carry, emit sum % 10, and keep sum / 10 as the new carry. Digits are at most 9, so the carry is always 0 or 1.

The detail I'd emphasise is the loop condition: l1 != null || l2 != null || carry != 0. That last clause is essential, because the result can be longer than both inputs — 99 plus 1 is 100. Without it the final carry is silently dropped.

I build the output behind a dummy head so appending needs no first-node branch.

O(max(n, m)) time, O(1) space beyond the result.

Worth saying why I'm not converting to a number: 100 digits overflows long by 80 orders of magnitude. The linked list is the representation because the value doesn't fit in a primitive."

Edge cases to volunteer:

Name [9,9] + [1]. It's the final-carry case, it's the bug everyone writes, and demonstrating it unprompted shows you thought about termination rather than just the happy path.

7. Follow-Up Questions — Modified Constraints

⭐ "What if the digits were stored most-significant-first?"

LeetCode 445. The natural direction for addition is now the wrong end of the list. Three options: reverse both lists, add, reverse the result — O(1) space but it mutates the inputs; push both onto stacks and pop, which gives least-significant-first without mutating, at O(n) space; or recurse to the end and add as the stack unwinds, which is the same O(n) space in disguise. I'd offer the stack version, since it's the clearest and leaves the inputs intact.

⭐ "Subtract instead of add."

Borrow replaces carry, and two new problems appear: you must first determine which number is larger (compare lengths, then digits from the most significant end) so you can subtract the smaller from the larger and negate, and you must strip the leading zeros that subtraction produces — 1000 - 999 = 1, not 0001. Meaningfully harder than addition, and worth saying so.

"Multiply the two numbers."

Schoolbook long multiplication over the digit lists, O(n·m). Accumulate into an array of size n + m indexed by place value, then propagate carries once at the end — simpler than carrying at every partial product. For very large n you'd reach for Karatsuba or FFT-based multiplication.

"What if each node held a 4-digit chunk instead of one digit?"

Same algorithm with base 10,000: digit = sum % 10000, carry = sum / 10000. It's 4× fewer nodes and 4× fewer iterations, which is roughly how real bignum libraries store values — in machine-word-sized limbs rather than decimal digits. The carry bound changes but stays 0 or 1.

"Add three or more lists."

The same loop with a list of input pointers. The only real change is the carry bound: with k addends, sum <= 9k + carry, so the carry can exceed 1 and sum / 10 may be several. The code survives unchanged, but the assumption "carry is 0 or 1" does not — which is exactly why it's worth having stated it as an assumption rather than a fact.

"What if the lists could be negative, with a sign node at the head?"

Compare magnitudes first, then dispatch to add or subtract and apply the resulting sign. This is where you'd stop and argue for BigInteger in real code — the number of sign and borrow cases grows fast, and it's well-trodden library territory.