Add Two Numbers as Linked Lists: The Dummy Node + Carry Trick
This is one of the most frequently asked linked list problems in coding interviews — and for good reason. It tests your understanding of linked list traversal, digit-by-digit arithmetic, and the carry-forward mechanism from grade-school addition. The twist: the digits are stored in reverse order, which actually makes the algorithm cleaner since the least-significant digit comes first, matching how addition works naturally.
The Key Insight: Simulate Column Addition
Think of adding 342 + 465 one column at a time, right to left. The linked list representation gives you exactly that order: [2→4→3] represents 342, [5→6→4] represents 465. Walk both lists together, add corresponding digits plus any carry, and build the result list as you go:
// [2→4→3] + [5→6→4]
// Position 1: 2 + 5 + carry(0) = 7 → digit 7, carry 0
// Position 2: 4 + 6 + carry(0) = 10 → digit 0, carry 1
// Position 3: 3 + 4 + carry(1) = 8 → digit 8, carry 0
// Result: [7→0→8] → represents 807 ✓
The Dummy Node Pattern
Using a dummy head node simplifies the code: you never need special-case logic for the first node. Just build the list starting at dummy.next, and return dummy.next at the end.
Code Implementation
function ListNode(val, next = null) {
this.val = val;
this.next = next;
}
function addTwoNumbers(l1, l2) {
const dummy = new ListNode(0);
let current = dummy;
let carry = 0;
// Continue while either list has nodes OR there's a carry remaining
while (l1 !== null || l2 !== null || carry !== 0) {
const val1 = l1 ? l1.val : 0; // use 0 if list is exhausted
const val2 = l2 ? l2.val : 0;
const sum = val1 + val2 + carry;
carry = Math.floor(sum / 10); // 0 or 1 (digit sum max is 9+9+1=19)
const digit = sum % 10;
current.next = new ListNode(digit);
current = current.next;
if (l1) l1 = l1.next;
if (l2) l2 = l2.next;
}
return dummy.next;
}
// Test: [2,4,3] + [5,6,4] = [7,0,8] (342 + 465 = 807)
// Test: [9,9,9,9,9,9,9] + [9,9,9,9] = [8,9,9,9,0,0,0,1] (9999999 + 9999 = 10009998)
Why the Loop Condition Includes carry !== 0
After both lists are exhausted, there may still be a carry of 1 (e.g., adding [5] + [5] = [0, 1]). Without || carry !== 0 in the condition, you'd miss this final digit — a common bug.
// [5] + [5]: 5 + 5 = 10 → digit 0, carry 1
// Both lists now null, but carry=1 → need one more iteration
// → digit 1, carry 0
// Result: [0→1] → represents 10 ✓
Complexity Analysis
- Time: O(max(m, n)) — one pass through the longer list (plus one extra step if there's a final carry).
- Space: O(max(m, n)) — the result list has at most max(m, n) + 1 nodes.
Key Takeaways
- Reversed digit order is a feature, not a bug — it lets you add least-significant digits first, matching natural arithmetic.
- The dummy head node pattern eliminates special-case code for the first node.
- Always check for a remaining carry after both lists are exhausted.
- Handle different-length lists by treating exhausted nodes as contributing 0.
What to Learn Next
This problem introduces the dummy node pattern and carry arithmetic — both appear again in multiply strings and add binary problems. Next, explore reversing a linked list (the foundational linked list operation), then tackle merge two sorted lists, which uses similar two-pointer simultaneous traversal but builds on sorted order instead of arithmetic.
