Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Walk both lists together adding digit-by-digit, exactly like grade-school addition. Keep a running `carry`, compute `sum = l1.val + l2.val + carry`, append `sum % 10` as a new node, and set `carry = sum / 10`. Use a dummy head so you never special-case the first node, and keep looping while either list has digits left OR carry is non-zero — that last condition is what appends the final carry node. O(max(m, n)) time, O(max(m, n)) space for the result list.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you can manage a carry cleanly across unequal-length lists and remember to emit the final carry node — plus whether you reach for a dummy head instead of fiddly first-node special-casing.
Where candidates slip
Stopping the loop when both lists are exhausted but forgetting the leftover carry (so 5 + 5 returns [0] instead of [0, 1]), or crashing on l1.val / l2.val when one list is already null.
How to stand out
Use a dummy head and the single unified `while l1 or l2 or carry` condition so unequal lengths and the final carry all fall out of one loop. Name the grade-school-addition analogy and connect it to Add Two Numbers II and Multiply Strings.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewAdd two numbers stored as linked listsDigit order?Least-significant first (reversed)Most-significant firstExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 1 · Optimal
Elementary Addition — Dummy Head + Carry (Optimal)
1Hint 1Explore hintHide hint
The digits are reversed, so the heads of both lists are the ones place. That's the column you'd add first by hand. What do you carry into the next column?
2Hint 2Explore hintHide hint
Keep a running carry. At each step compute sum = digit1 + digit2 + carry, append sum % 10 as a new node, and set carry = sum / 10. Treat a missing digit as 0.
3Hint 3Explore hintHide hint
Loop while EITHER list still has nodes OR carry is non-zero — that last clause appends the final carry node. Use a dummy head and return dummy.next so the first node needs no special case.
A · Core idea
We reproduce exactly what you do when adding two numbers on paper, except the lists hand us the digits in the most convenient order possible: least-significant first. We walk both lists in lockstep, and at each column we add the two digits plus whatever carry came from the previous column.
Why the reversed order is a gift, not a hassle. Long addition starts at the ones place and carries leftward into higher place values. Because the lists are stored least-significant-first, the head is the ones place and next walks toward higher places — the exact direction the carry needs to flow. So we add front-to-back, append each result digit to the back of the output, and the carry naturally rides forward. If the digits were most-significant-first we'd have to reverse or use stacks; here we get the right direction for free.
Why the dummy head earns its keep. Building a list by appending always has an annoying first-node problem: the head pointer is null at the start, so the first append needs different code than the rest. A dummy (sentinel) node sidesteps this entirely. We point curr at the dummy, always do curr.next = new node; curr = curr.next, and at the end return dummy.next — the real first digit. Every iteration uses identical code, which means fewer branches and fewer bugs.
Why the loop condition is `l1 OR l2 OR carry`. Three things can keep the addition alive: digits left in l1, digits left in l2, or a pending carry. Using OR means the loop runs until all three are exhausted. The carry term is the subtle one — consider 5 + 5. Both lists empty after one column, but carry is 1, so the loop runs one more time with both digits treated as 0, producing the leading 1 node. Drop the carry clause and 5 + 5 wrongly returns [0] instead of [0, 1].
Why missing digits become 0. Unequal lengths are handled with x = l1.val if l1 else 0. Once the shorter list runs out, its contribution is 0 for the remaining columns — precisely how you'd pad a shorter number with leading zeros on paper. This collapses what could be three phases (both lists, then leftover of one, then carry) into a single clean loop.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
l1 = [2, 4, 3], l2 = [5, 6, 4] (342 + 465)Interactive diagram
Carry rippling through the columns
col 0Each box is one column add. The red carry edge feeds the next column; the final carry spawns a new node.
[7, 0, 8] (807)C · Code with teaching comments
D · Why it works and complexityO(max(m, n)) timeO(max(m, n)) spaceOpen the invariant and proofExplore the proofHide the proof
The entire problem is one loop guarded by l1 or l2 or carry, with every awkward case — unequal lengths, the trailing carry, the first-node append — absorbed into that single condition plus a dummy head. When a build-a-list problem tempts you into multiple cleanup loops, look for the unified condition that makes them disappear.
ComplexityO(max(m, n)) time, O(max(m, n)) space — We touch each node of the longer list exactly once doing O(1) arithmetic → O(max(m, n)) time. The result list has at most max(m, n) + 1 nodes → O(max(m, n)) space (output only; the carry and pointers are O(1)).
E · Edge cases and pitfalls7l1 = [5], l2 = [5] — Column 0: 5+5=10 → append 0, carry 1. Lists now empty but carry=1 → loop once more, append 1. Result [0, 1]. This is the final-carry case.Explore edge casesHide edge cases
Edge cases handled
l1 = [5], l2 = [5]Column 0: 5+5=10 → append 0, carry 1. Lists now empty but carry=1 → loop once more, append 1. Result [0, 1]. This is the final-carry case.l1 = [0], l2 = [0]Single column 0+0=0, carry 0 → result [0]. Confirms we don't strip a legitimate single zero.l1 = [9, 9], l2 = [1]col0: 9+1=10 → 0 carry 1; col1: 9+0+1=10 → 0 carry 1; carry left → append 1. Result [0, 0, 1] (99 + 1 = 100).
Pitfalls
- Ending the loop on `l1 != null && l2 != null` instead of `||` — drops the longer list's tail and the final carry.
- Forgetting the carry clause in the loop condition — 5 + 5 returns [0] instead of [0, 1].
- Reading l1.val / l2.val without a null guard — crashes once the shorter list is exhausted.
- Converting the lists to integers and adding — overflows for 100-digit inputs.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; }Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Forgetting the final carry node
When the last column produces a carry (e.g. the most-significant digits sum to ≥ 10), the leftover carry is a brand-new most-significant digit. If the loop stops as soon as both lists are empty, that digit is lost.
Explore the code comparisonHide the code comparison
Forgetting the final carry node
When the last column produces a carry (e.g. the most-significant digits sum to ≥ 10), the leftover carry is a brand-new most-significant digit. If the loop stops as soon as both lists are empty, that digit is lost.
Don't write this
while l1 and l2:
total = l1.val + l2.val + carry
carry = total // 10
curr.next = ListNode(total % 10)
curr = curr.next
l1, l2 = l1.next, l2.next
return dummy.next # drops longer tail AND final carryWrite this instead
while l1 or l2 or carry:
x = l1.val if l1 else 0
y = l2.val if l2 else 0
total = x + y + carry
carry = total // 10
curr.next = ListNode(total % 10)
curr = curr.next
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
return dummy.next2Null-pointer on the shorter list
Once the shorter list is exhausted its pointer is null. Reading .val or advancing it unconditionally crashes. Guard both the read (default to 0) and the advance.
Explore the code comparisonHide the code comparison
Null-pointer on the shorter list
Once the shorter list is exhausted its pointer is null. Reading .val or advancing it unconditionally crashes. Guard both the read (default to 0) and the advance.
Don't write this
while (l1 != null || l2 != null) {
int sum = l1.val + l2.val + carry; // NPE when one is null
...
l1 = l1.next;
l2 = l2.next;
}Write this instead
while (l1 != null || l2 != null || carry != 0) {
int x = (l1 != null) ? l1.val : 0;
int y = (l2 != null) ? l2.val : 0;
int sum = x + y + carry;
...
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}3Hand-rolling the first node instead of a dummy head
Without a sentinel you must branch on whether the head exists yet on every append, which is verbose and a frequent source of off-by-one head bugs.
Explore the code comparisonHide the code comparison
Hand-rolling the first node instead of a dummy head
Without a sentinel you must branch on whether the head exists yet on every append, which is verbose and a frequent source of off-by-one head bugs.
Don't write this
ListNode head = null, curr = null;
while (...) {
ListNode node = new ListNode(sum % 10);
if (head == null) { head = node; curr = node; }
else { curr.next = node; curr = node; }
}
return head;Write this instead
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while (...) {
curr.next = new ListNode(sum % 10);
curr = curr.next;
}
return dummy.next;Revise
Carry the pattern into the interview
Pattern to remember
Elementary-school addition over a dummy-headed result list
Code pattern to memorize
dummy = ListNode(0)
curr = dummy
carry = 0
while l1 or l2 or carry:
x = l1.val if l1 else 0
y = l2.val if l2 else 0
s = x + y + carry
carry = s // 10
curr.next = ListNode(s % 10)
curr = curr.next
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
return dummy.nextRules to remember
- 1Digits are stored in reverse order, so the list head is the ones place — you add left-to-right and the carry flows naturally forward.
- 2Loop while
l1 OR l2 OR carry— the carry term is what appends the leftover final node (e.g. 5 + 5 = 10 →[0, 1]). - 3Use a dummy head node and return
dummy.next; it removes the 'is this the first node?' special case entirely. - 4Treat a missing digit as 0 (
l1.val if l1 else 0) so unequal lengths just work without a separate cleanup loop. - 5
carryis always 0 or 1 when adding two base-10 digits (max 9 + 9 + 1 = 19), but writes // 10rather than hard-coding it. - 6Advance
l1/l2only if they're non-null — guarding the advance is what lets one list run out before the other.
Use this pattern when
- Adding, subtracting, or multiplying numbers represented as linked-list digits
- Any per-element merge of two lists where positions line up and you carry state forward
- You need to build a brand-new result list while consuming two inputs in lockstep
- Reverse-order digit storage makes least-significant-first processing natural
Choose another pattern when
- Digits stored most-significant-first → reverse first, or use a stack (Add Two Numbers II)
- Numbers fit in a 64-bit integer and you may convert → just parse, add, rebuild (usually disallowed here)
- You must not allocate new nodes → in-place is awkward; this problem expects a fresh list
Interview takeaway
This is the canonical 'build a new list with a dummy head while carrying state forward' problem. The dummy-head + `while a or b or carry` shape recurs in Merge Two Sorted Lists, Add Two Numbers II, and Multiply Strings — master the carry-and-append rhythm once and reuse it everywhere.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical 'build a result list with a dummy head while carrying state forward'. The `while a or b or carry` loop is the same skeleton as Merge Two Sorted Lists and Add Binary. Recognise it whenever two sequences are combined position-by-position with a value that propagates to the next position.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Add Two Numbers IIComing soonDigits are most-significant-first. Reverse both lists or push onto stacks so you can still add least-significant-first.
- Merge Two Sorted ListsSame dummy-head + lockstep-walk skeleton, but you pick the smaller node instead of summing digits.
- Multiply StringsComing soonGeneralises carry handling to multiplication; accumulate partial products with carries into a digit buffer.
- Add BinaryComing soonIdentical carry-forward logic on two binary strings — carry is 0 or 1, write sum % 2, carry sum / 2.