Add Two Numbers

Two reversed-digit lists are already aligned for grade-school addition — walk both once, one column per step, and let a single carry bit remember everything.

The memory hook

Add one column at a time and let a single carry bit remember everything.

MediumSingle pass + carryO(max(m, n)) timeO(max(m, n)) space

Reversed order is a gift

intuition

On paper you add from the ones column upward, but numerals are written most-significant-first — so you must start at the far end. Here LeetCode already flipped the lists: the head is the ones digit. That turns addition into a single left-to-right walk with one bit of memory.

1Line up the columnsPosition i of both lists is the 10^i column. Walk both pointers together; a missing node on the short list simply reads as 0.

2Write digit, keep carryColumn total s = x + y + carry. The digit s % 10 goes on a new node; floor(s / 10) — always 0 or 1 — becomes the next carry.

3Flush the last carryIf a carry survives past both tails (e.g. 5 + 5), append one final node. The loop test while l1 or l2 or carry handles it for free.

The one sentence to remember: After writing column i, the result holds the exact sum of the lowest i+1 digits and carry is the overflow into column i+1 — that is the whole invariant.

Watch one column become one node

playable trace

Step through 342 + 465 digit by digit. Each frame writes exactly one result node and updates the carry chip — the only state the walk remembers.

Playable trace · Single pass + carry

Frames are generated from the same logic as the code below.

Presets

Current event

Ready — press Play

Result so far

Carry

Both pointers start at the heads — the ones column. Press Play.

unread current column complete missing node = 0 result digit

0 / 0 speed 650ms

One loop, one carry

the solution

Python · Single pass + carry

class Solution:
    def addTwoNumbers(self, l1, l2):
        dummy = ListNode(0)  # sentinel: never moves; dummy.next is the answer
        cur, carry = dummy, 0
        while l1 or l2 or carry:  # carry in the test emits the final node
            x = l1.val if l1 else 0  # a missing node reads as 0
            y = l2.val if l2 else 0
            s = x + y + carry
            cur.next = ListNode(s % 10)  # this column's digit
            carry = s // 10  # 0 or 1: the only state kept
            cur = cur.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
        return dummy.next

The displayed Python and the trace above use the same boundary logic: missing node = 0, carry folded into the loop test.

Unequal lengthsx = l1.val if l1 else 0The short list contributes 0 once exhausted — no padding pass, no length precompute needed.

Carry rangecarry = s // 10 ∈ {0, 1}Max column total is 9 + 9 + 1 = 19, so the carry is always a single bit. That is why O(1) extra state suffices.

Trailing carrywhile l1 or l2 or carryPutting carry in the loop condition appends the final node (5 + 5 → [0, 1]) with no special-case code after the loop.

Why is this always right? Induction on the invariant: each column writes floor-correct digit s % 10 for its place value and forwards exactly the overflow s // 10. When the loop exits, both lists are drained and no overflow remains, so every digit is final.

TimeO(max(m, n))each node visited once — one step per column of the longer list.

SpaceO(max(m, n))one output node per result digit; only carry + a few pointers besides.

Two quick mental checks

make it stick

l1 = [2,4,3], l2 = [5,6,4]

→ [7,0,8]

342 + 465 = 807. The tens column 4 + 6 = 10 writes 0 and carries 1 into the hundreds — the carry chip lighting up is the moment to watch.

l1 = [9×7], l2 = [9×9×9×9]

→ [8,9,9,9,0,0,0,1]

9,999,999 + 9,999 = 10,009,998. The carry ripples through four columns then dies — then the loop runs three more silent columns before both lists end.

What to say out loud

Reversed order means the head is the ones digit, so I walk both lists once: each column writes one node with s mod 10 and forwards s over 10 as the carry. Missing nodes read as zero, and the carry in the loop condition emits the final node.