TL;DR
Single-pass grade-school addition with a carry — O(max(n, m)) time, O(1) extra space beyond the output.
Approach 1 — Brute force: convert to integers, add, convert back
Read each list into a Python int (reversing the digit order), add, then peel digits off the sum.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
from typing import Optional
def addTwoNumbers(
self, l1: Optional[ListNode], l2: Optional[ListNode]
) -> Optional[ListNode]:
def to_int(node: Optional[ListNode]) -> int:
num, place = 0, 1
while node:
num += node.val * place
place *= 10
node = node.next
return num
total = to_int(l1) + to_int(l2)
dummy = ListNode()
tail = dummy
while True:
tail.next = ListNode(total % 10)
tail = tail.next
total //= 10
if total == 0:
break
return dummy.next
Complexity: O(n + m) time in list length, but each big-int operation on a 100-digit number is not constant — arithmetic costs grow with digit count, so this is really O((n+m)^2)-ish bit work. Space O(1) beyond the output.
Python’s unlimited ints let this run, but up to 100 digits is why the approach fails in most languages: a 64-bit integer overflows at 19 digits. The interviewer expects the digit-by-digit simulation below.
Approach 2 — Elementary-school addition with a carry (one pass)
The lists store digits least-significant-first, which is the order column addition proceeds. Walk both lists in lockstep, keep a single carry in {0, 1}, and emit (d1 + d2 + carry) % 10 per position. Treat an exhausted list as contributing 0, and keep looping while a carry remains. This handles different lengths and the extra final digit with one condition.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
from typing import Optional
def addTwoNumbers(
self, l1: Optional[ListNode], l2: Optional[ListNode]
) -> Optional[ListNode]:
dummy = ListNode()
tail = dummy
carry = 0
while l1 or l2 or carry:
d1 = l1.val if l1 else 0
d2 = l2.val if l2 else 0
carry, digit = divmod(d1 + d2 + carry, 10)
tail.next = ListNode(digit)
tail = tail.next
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
return dummy.next
Walkthrough on l1 = 2 -> 4 -> 3, l2 = 5 -> 6 -> 4 (342 + 465). Each list holds one digit per node, least significant first:
flowchart LR
subgraph L1 ["l1 = 342"]
direction LR
a1["2"] --> a2["4"] --> a3["3"]
end
subgraph L2 ["l2 = 465"]
direction LR
b1["5"] --> b2["6"] --> b3["4"]
end
subgraph OUT ["sum = 807"]
direction LR
c1["7"] --> c2["0"] --> c3["8"]
end
| position | d1 | d2 | carry in | sum | digit out | carry out |
|---|
| ones | 2 | 5 | 0 | 7 | 7 | 0 |
| tens | 4 | 6 | 0 | 10 | 0 | 1 |
| hundreds | 3 | 4 | 1 | 8 | 8 | 0 |
Both lists and the carry are exhausted → output 7 -> 0 -> 8, i.e. 807. On 999 + 1, after three positions the lists are empty but carry = 1, so the loop runs once more and appends the leading 1.
Complexity: O(max(n, m)) time, O(1) space beyond the output list of max(n, m) + 1 nodes.
Approach 3 — Recursive version
The same column addition, expressed recursively: each call produces one digit node and delegates the rest of both lists plus the carry to the next call. Base case: both lists empty and no carry.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
from typing import Optional
def addTwoNumbers(
self, l1: Optional[ListNode], l2: Optional[ListNode]
) -> Optional[ListNode]:
def add(a: Optional[ListNode], b: Optional[ListNode], carry: int):
if not a and not b and carry == 0:
return None
total = (a.val if a else 0) + (b.val if b else 0) + carry
node = ListNode(total % 10)
node.next = add(
a.next if a else None,
b.next if b else None,
total // 10,
)
return node
return add(l1, l2, 0)
Walkthrough on 0 + 0: the first call computes total = 0, emits node 0, and recurses with two empty lists and carry 0 — the base case returns None, so the answer is the single node 0.
Complexity: O(max(n, m)) time, O(max(n, m)) space for the call stack — fine at 100 digits, but the iterative loop is strictly better on space.
Common pitfalls
- Loop condition
while l1 and l2 (stops at the shorter list) or while l1 or l2 (drops a final carry — 999 + 1 returns 0,0,0). It must be l1 or l2 or carry.
- Advancing
l1/l2 unconditionally after the shorter one is exhausted — None.next raises.
- Reversing the lists first “to make it feel like normal numbers” — unnecessary work; the given order is already the right one.
- Emitting the carry as a digit mid-loop instead of folding it into the next column’s sum.
Pattern takeaway
When a number arrives as a digit sequence, don’t round-trip through an integer type — simulate the arithmetic column by column with a carry. The uniform trick “missing digit = 0, loop while anything (including the carry) remains” collapses all the length-mismatch and final-carry edge cases into one loop condition, and it reappears in Add Binary, Plus One, and Multiply Strings.