Think of grade-school column addition: stack two numbers, add from the rightmost column forward, write down the ones digit, and carry any overflow into the next column. These two linked lists are already laid out from the ones place forward — each node is a column. Walk both chains in lockstep with a carry variable, summing each pair of digits plus the incoming carry. The ones place of that sum becomes the next result node; the tens place carries forward. A dummy head avoids the first-node edge case. When one chain runs out, treat its missing digits as zero. When both are exhausted, any leftover carry becomes a final node. One pass. O(max(m, n)) time. O(1) extra space beyond the result.
The algorithm processes both lists simultaneously, one position at a time. At each column, three values contribute to the sum: the digit from the first list, the digit from the second list, and the carry from the previous column.
At each position, compute l₁.val + l₂.val + carry.
The ones digit (sum % 10) becomes the output node's value.
The tens digit (sum / 10) becomes the carry for the next column.
This mirrors exactly how pencil-and-paper addition works.
Carry can only be 0 or 1 — the maximum column sum is 9 + 9 + 1 = 19.
The carry flows forward until both lists are exhausted and the
carry is zero. This three-part termination condition
(l₁ || l₂ || carry) is what creates the final node when
the sum has more digits than either input.
A temporary sentinel node created before the loop. Every output digit
is attached through tail.Next — including the first. No
special-case logic for the empty result. At the end,
dummyHead.Next gives the real head of the sum list.
The main loop runs while either list has remaining nodes or a carry is pending. Each iteration consumes one node from each list (if available), computes the column sum, and emits a single output digit.
Create a dummy head node. Set tail = dummyHead and
carry = 0. Both input pointers start at their respective heads.
While l₁ ≠ null || l₂ ≠ null || carry > 0:
read the current digit from each list (or 0 if that list is exhausted).
Add the two digits and the incoming carry:
columnSum = l₁.val + l₂.val + carry.
Create a new node with value columnSum % 10.
Attach it via tail.Next and advance tail.
Set carry = columnSum / 10.
Move each non-null input pointer to its next node. If a list has already ended, it continues to contribute 0.
Return dummyHead.Next — the first real node of the
sum list. The dummy head is discarded.
Three situations push beyond the basic case. The loop's termination
condition — l₁ || l₂ || carry — handles all of them
without special branches.
When one list is shorter, it runs out first. The algorithm treats its
missing digits as 0 — the remaining columns simply add the longer
list's digit to the carry. No padding or alignment is needed because
the null-coalescing (l?.val ?? 0) handles it inline.
Try the "[2,4,3] + [5]" preset.
When every column produces a carry, the overflow ripples through the entire sum. Adding 999 + 1 produces carries at every position until a final carry creates a new most-significant digit. The loop continues as long as carry is nonzero, even after both lists are exhausted. Try the "[9,9,9] + [1]" preset.
When the last column produces a carry, the result has more digits than either input. The loop runs one extra iteration with both list pointers null — only the carry contributes. This creates the most-significant digit of the sum. Try the "[5] + [5]" preset.