Add Two Numbers

The lists already expose digits in the order addition needs. Scan both lists together, track one carry, and keep going until there is no digit or carry left.

Read the representation before choosing the algorithm

Each node stores one decimal digit, and the digits appear least significant first. A list such as:

2 → 4 → 3

represents 342, not 243.

That representation is the decisive clue. Schoolbook addition starts with the ones place, then moves toward larger place values. The linked list starts with the ones place, then moves toward larger place values. A head-to-tail scan is already the correct arithmetic direction.

For example:

342 + 465 = 807

The lists are:

l1: 2 → 4 → 3
l2: 5 → 6 → 4

Process them in that order:

1. 2 + 5 = 7
2. 4 + 6 = 10: emit 0, carry 1
3. 3 + 4 + 1 = 8

The result is:

7 → 0 → 8

This solution has four obligations:

• Process one digit position at a time.
• Treat a missing digit from a shorter list as zero.
• Emit each result digit in reverse order.
• Preserve a carry that may create one extra node after both lists end.

The important observation is that the input representation has already removed the need to reverse anything. Reversing the lists, converting them into whole integers, or storing all digits elsewhere adds machinery around a problem that is already arranged for streaming.

Choose the direct baseline

A whole-number conversion approach would read every digit, reconstruct both integers, add them, and convert the result back into a linked list. That is the wrong baseline for an interview solution because it abandons the supplied representation and hides the state that actually matters.

Reversing the lists or using stacks would make sense if the digits were stored most significant first. Here, those techniques solve a different representation problem.

The direct method is schoolbook addition over two streams:

• Read one digit from each stream.
• Add the incoming carry.
• Emit the current result digit.
• Pass the new carry to the next position.

There is no need for recursion or a preliminary length pass. We can process both lists in one traversal, even when their lengths differ.

Derive the carry state and invariant

The minimal useful state is small:

• l1: pointer to the next digit in the first list
• l2: pointer to the next digit in the second list
• carry: value passed from the previous position
• tail: end of the result list
• dummy: placeholder node before the real result

At each iteration, read a digit when its pointer exists. Otherwise, use zero:

digit1 = l1.val if l1 exists, otherwise 0
digit2 = l2.val if l2 exists, otherwise 0

Then calculate:

total = digit1 + digit2 + carry
emitted_digit = total % 10
next_carry = total // 10

For decimal addition, % 10 keeps the digit for the current position, while // 10 extracts the amount passed to the next position.

The key invariant is:

After each iteration, the result prefix is correct for every processed digit position, and carry is exactly the value that must be added to the next position.

This explains why earlier digits can be discarded. Once a result digit has been emitted, its value is fixed. All influence from the processed prefix that can affect future positions has been compressed into carry.

That is state tracking in its cleanest form: discard what is finished, preserve only what can still change the future.

Make termination an explicit obligation

The loop condition must represent unfinished work:

while l1 or l2 or carry:

Work remains when:

• l1 still points to a digit,
• l2 still points to a digit, or
• carry still requires another output node.

The third condition is easy to miss. Consider:

99 + 1 = 100

The lists are:

l1: 9 → 9
l2: 1

The iterations are:

Position	Digit from l1	Digit from l2	Carry in	Total	Output digit	Carry out
1	9	1	0	10	0	1
2	9	0	1	10	0	1
3	0	0	1	1	1	0

The result is:

0 → 0 → 1

After the second input node is consumed, the carry is still real work. Stopping when both pointers are null would return 0 → 0 and lose the leading 1.

The common incorrect conditions are:

while l1 and l2:

This stops as soon as either list ends, so it loses the remaining digits of the longer list.

while l1 or l2:

This handles unequal lengths but loses a final carry.

The correct condition is derived from the problem's obligations, not memorized as a list trick: continue while any input digit or pending carry remains.

Build the Python result with a dummy tail

A dummy node is a construction tool. It sits before the real answer so every output node—including the first—can be attached with the same operation:

tail.next = new_node
tail = tail.next

Without it, the first output node needs a special case: initialize the head, then use different logic for later nodes. That special case carries no algorithmic value and creates another place for pointer bugs.

Assuming the standard ListNode abstraction, the Add Two Numbers Python implementation is:

from typing import Optional


class Solution:
    def addTwoNumbers(
        self,
        l1: Optional["ListNode"],
        l2: Optional["ListNode"],
    ) -> Optional["ListNode"]:
        dummy = ListNode(0)
        tail = dummy
        carry = 0

        while l1 or l2 or carry:
            total = carry

            if l1:
                total += l1.val
                l1 = l1.next

            if l2:
                total += l2.val
                l2 = l2.next

            carry = total // 10
            digit = total % 10

            tail.next = ListNode(digit)
            tail = tail.next

        return dummy.next

Each state variable maps directly to an obligation:

• l1 and l2 identify the next input positions.
• carry transports influence between positions.
• total combines the current digits with that influence.
• digit is the one output value for the current position.
• tail preserves the construction point.
• dummy.next skips the placeholder and returns the real result.

Notice that the input pointers advance independently. If l1 is exhausted, l2 can continue contributing digits. The absent value from l1 is represented by leaving total unchanged.

Trace the state on ordinary addition

For 342 + 465, the lists are 2 → 4 → 3 and 5 → 6 → 4.

Position	l1 digit	l2 digit	Carry in	Total	Emitted digit	Carry out
1	2	5	0	7	7	0
2	4	6	0	10	0	1
3	3	4	1	8	8	0

The result nodes are appended in exactly the order they are computed:

7 → 0 → 8

That represents 807, the correct sum.

Now change the lengths. For 243 + 56:

l1: 3 → 4 → 2
l2: 6 → 5

The third iteration reads 2 from l1 and treats the exhausted l2 as zero. No alignment code is needed. The pointers themselves define the current position, and missing input contributes nothing.

One transition handles all three situations:

1. Both lists still have digits.
2. Only one list still has digits.
3. Both lists are empty but carry remains.

That uniformity is a sign that the state model is correct.

Prove correctness and analyze complexity

The correctness argument follows the invariant.

Initialization: Before processing any digits, the result contains no real nodes, so its processed prefix is correctly empty. The initial carry is zero.

Maintenance: Suppose the invariant holds before an iteration. The current pointers identify the next unprocessed digit in each list. Missing digits contribute zero. Adding those values and the incoming carry gives the correct arithmetic total for the current position. total % 10 is the digit that belongs at that position, and total // 10 is the carry required by the next position. Appending the emitted digit extends the correct result prefix by one position.

Termination: The loop stops only when both input pointers are null and carry is zero. Therefore, no input digit and no pending carry remains unprocessed. The result contains every required output position.

The output order is also correct by construction. The inputs expose least significant digits first, so the algorithm emits least significant result digits first. The returned list uses the same representation.

If the input lengths are m and n, the loop runs at most:

max(m, n) + 1

times, where the extra iteration handles a final carry. Therefore:

• Time: O(max(m, n))
• Auxiliary state: O(1)
• New output storage: O(max(m, n) + 1) in the final-carry case

The constant-size state excludes the result list itself. The algorithm does not count output nodes as auxiliary workspace, but it does allocate them because the problem requires a new linked-list result.

Test the failure boundaries

Good tests target the obligations, not just the happy path.

Single-digit addition without carry

2 + 5 = 7

This checks basic node creation and the zero-carry path.

Carry propagation

99 + 1 = 100

Expected representation:

0 → 0 → 1

This checks repeated carry propagation and the final carry-only iteration. Also try 999 + 1 to force a longer chain.

Unequal lengths in both directions

243 + 56
56 + 243

The result should be the same in both orders. These cases verify that each pointer advances independently and that an exhausted list contributes zero.

Zero values

0 + 0 = 0

The result should contain one zero node under the problem's representation rules. Do not accidentally return the dummy node itself.

Pointer and construction checks

When debugging, inspect these independently:

• A missing node contributes 0, not an error.
• l1 advances only when l1 is non-null.
• l2 advances only when l2 is non-null.
• The first real result node is dummy.next.
• A carry is updated before the next iteration.
• The loop includes carry-only work.

These checks catch the failures that examples often hide: dropped suffix digits, skipped nodes, a lost first node, and a missing final carry.

The transferable pattern

The durable lesson is larger than linked-list arithmetic:

When a representation exposes the next required position in scan order, simulate the operation with the smallest state that crosses positions.

Here, the representation gives us least-significant digits first. The necessary state is two input pointers, one carry, and a result tail. The invariant tells us what remains true after every step. The termination condition lists every kind of unfinished work.

Before coding, ask three questions:

1. What does the next node or element represent?
2. What information must survive from one position to the next?
3. What work remains when the main inputs are exhausted?

Answer those first. Then the implementation becomes a short transcription of the reasoning instead of a pointer puzzle.