Understanding the Problem: Adding Numbers Stored as Linked Lists
This is a classic linked list problem that tests your ability to simulate grade-school addition at the node level. The digits are stored in reverse order — the head of each list holds the least significant digit (the ones place) — which actually makes the addition logic more natural, since you always start adding from the ones place.
The key challenge is managing the carry: when two digits sum to 10 or more, you carry the 1 to the next position, just like you would on paper.
The Core Insight: Simulate Long Addition
Walk through both lists simultaneously, adding digit pairs one position at a time:
- At each step, compute
sum = digit1 + digit2 + carry. - The new node's value is
sum % 10(the ones digit of the sum). - The carry to the next position is
sum // 10(either 0 or 1). - When one list runs out, treat its missing digits as 0.
- After both lists are exhausted, if carry is still 1, add one final node.
Step-by-Step Algorithm
- Create a dummy head node — a placeholder that simplifies list-building (you return
dummy.nextat the end). - Initialize
carry = 0and acurrentpointer starting at the dummy node. - Loop while at least one list still has nodes, or carry is non-zero:
- Read the current node's value (or 0 if that list is exhausted).
- Compute
total = val1 + val2 + carry. - Set
carry = total // 10; create a new node with valuetotal % 10. - Advance both input pointers (if they haven't reached None).
- Return
dummy.next.
Code Implementation
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def addTwoNumbers(l1, l2):
dummy = ListNode() # placeholder head
current = dummy
carry = 0
while l1 or l2 or carry:
val1 = l1.val if l1 else 0 # use 0 if list is exhausted
val2 = l2.val if l2 else 0
total = val1 + val2 + carry
carry = total // 10 # 0 or 1
current.next = ListNode(total % 10)
current = current.next
if l1: l1 = l1.next
if l2: l2 = l2.next
return dummy.next
Worked Example
# 342 + 465 = 807
# Lists: [2→4→3] + [5→6→4]
# Position 0 (ones): 2 + 5 + carry(0) = 7 → node(7), carry=0
# Position 1 (tens): 4 + 6 + carry(0) = 10 → node(0), carry=1
# Position 2 (hundreds): 3 + 4 + carry(1) = 8 → node(8), carry=0
# Result: [7→0→8] which represents 807 ✓
Complexity Analysis
- Time: O(max(n, m)) — We traverse each list once. The loop runs for as many iterations as the longer list (plus one more if there's a final carry).
- Space: O(max(n, m)) — The result list has at most max(n, m) + 1 nodes (the extra +1 accounts for a possible carry-out digit).
Edge Cases to Handle
# Lists of different lengths:
# [9,9] + [1] = 100 → [0→0→1]
# 99 + 1 = 100 ✓
# All nines + any number causes cascading carry:
# [9,9,9] + [1] = 1000 → [0→0→0→1]
# Single digit each:
# [5] + [5] = 10 → [0→1]
The loop condition while l1 or l2 or carry handles all these naturally — the final or carry ensures that a remaining carry always generates one last node.
The Dummy Node Trick
The dummy head is a common linked list pattern worth memorizing. Instead of special-casing the very first node, you build the result off a throw-away node and return dummy.next. This makes the loop uniform — every iteration just appends to current.next. You'll see this pattern in many linked list problems.
Key Takeaways
- Simulate grade-school addition: add digit pairs plus carry, position by position.
total % 10gives the digit to store;total // 10gives the carry forward.- Use a dummy head node to simplify list construction.
- The loop continues as long as either list has nodes or there's a carry — don't forget that last condition.
What to Learn Next
This problem builds on your understanding of linked list traversal and node manipulation. Next, explore similar linked list problems: Reverse Linked List (learn in-place reversal), Merge Two Sorted Lists (another two-pointer pattern), and Linked List Cycle (fast and slow pointer technique).
