Algorithm

Add Two Numbers

Linked List Pattern

Add Two Numbers

You are given two non-negative integers, each stored as a singly linked list of single digits with the ones digit at the head — the digits are in reverse order, so 342 is stored as 2 → 4 → 3. Return their sum in the same form: a new linked list of digits, ones-first. The two lists may have different lengths, and the result may be longer than both (a final carry adds one more digit). Neither input has leading zeros, except the number 0 itself, which is the single node [0].

CONSTRAINTS
  • The number of nodes in each list is in the range [1, 100]
  • 0 <= Node.val <= 9
  • No leading zeros except the number 0 itself.
EXAMPLE 1
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Reversed, the inputs are 342 and 465; their sum is 807, which stored ones-first is 7 → 0 → 8. The middle digit is 0 because 4 + 6 = 10 spills a carry into the next column.
EXAMPLE 2
Input: l1 = [0], l2 = [0]
Output: [0]
Both numbers are 0, so the sum is 0 — a single-digit result, [0].
EXAMPLE 3
Input: l1 = [9,9,9,9], l2 = [9,9,9]
Output: [8,9,9,0,1]
This is 9999 + 999 = 10998. The result has five digits — one more than the longer input — because the top column overflows and a final carry becomes its own leading digit.
Why are the digits stored in reverse order — is that a complication?
It's the opposite: reverse order puts the ones digit at the head, so walking forward from the heads processes columns least-significant first, which is the exact direction carries flow in hand addition. It removes work rather than adding it.
What if the two lists have different lengths?
Treat the shorter list's missing high-order digits as 0. A number like 45 is just 045 when you need a hundreds digit, so padding with zero keeps the column addition correct.
What happens if a carry remains after both lists are exhausted?
You must append one more node for it — that final carry is always 1 and it makes the result one digit longer than either input. This is exactly the case people forget, so the loop has to keep running while a carry is pending.
Can I just convert each list to an integer, add, and convert back?
Risky. Each number can be 100 digits, which overflows fixed-width integer types in most languages. Adding digit by digit in the given representation avoids the overflow entirely, so it's the robust approach.
The Parallel Adder

Adding numbers in linked lists is actually easier when they are reversed because the "ones" place comes first. This mirrors exactly how we perform long addition on paper: start at the right, add digits, and carry the overflow to the left.

Coordinated Stepping

We use a Dummy Node to build our result list. In each step, we sum the values of the current nodes from both lists plus any carry from the previous step. The new digit is sum % 10, and the new carry is sum // 10.

python
dummy = Node(0)
curr = dummy
carry = 0

while l1 or l2 or carry:
    v1 = l1.val if l1 else 0
    v2 = l2.val if l2 else 0
    
    # 1. Sum and Carry
    val = v1 + v2 + carry
    carry = val // 10
    
    # 2. Append result
    curr.next = Node(val % 10)
    curr = curr.next
    
    # 3. Step forward
    l1 = l1.next if l1 else None
    l2 = l2.next if l2 else None

return dummy.next
Worked Example:[2, 4] + [5, 6]
0
dummy/curr
→
NULL
We initialize a dummy head node containing 0 to start building our result list.
0
→
7
curr
→
NULL
We add the first digits: 2 (from l1) + 5 (from l2) + 0 (carry) = 7. We append 7 to our result list, leaving the carry at 0.
0
→
7
→
0
curr
→
NULL
We move to the next digits: 4 (from l1) + 6 (from l2) + 0 (carry) = 10. We append the digit 0 to the result list, and record a carry of 1.
0
→
7
→
0
→
1
curr
→
NULL
Both input lists are fully traversed. Since we still have a carry of 1, we append a final node containing 1 to the result list.
7
→
0
→
1
→
NULL
Finally, we return dummy.next, which is the head of our completed list [7, 0, 1] (representing the number 107).
Interactive Strategy Visualization

Digit-by-Digit Addition

Strategy: Two-Pointer Simulation
Memory: O(1) excluding output
List 1 (v1)
2
4
List 2 (v2)
5
6
Result
Operation
2 + 5 + 0 = 7
Carry Out
0
Digit for List
-
1. Summing the Ones
Add head nodes from both lists. Sum is 7, no carry needed.
O(max(N, M)) Time · O(max(N, M)) Space Column Addition with Carry