-
Notifications
You must be signed in to change notification settings - Fork 0
070 — Add Two Numbers
LeetCode 2 · Medium. You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each node contains a single digit. Add the two numbers and return the sum as a linked list, also in reverse order.
This is grade-school column addition, except the "columns" are handed to you least-significant-digit first — which, conveniently, is exactly the order you'd want to add them in by hand anyway (ones place first, then tens, then hundreds...). Walk both lists at the same time, add the two digits at each position plus whatever carried over from the previous position, write down the ones digit, carry the rest forward. When one list runs out of digits, keep going with the other (treating the missing digit as 0), and if there's a carry left over after both lists are exhausted, that becomes one final extra digit.
"Two linked lists" plus "add" plus digit-by-digit with a carry is the signal for walking both structures simultaneously, tracking one small piece of running state (the carry) between steps. Any time you're combining two sequences position-by-position rather than comparing them or merging by order, that's the same "advance both pointers together" shape as merging two sorted lists — just with arithmetic instead of comparison at each step.
Reconstruct each list as an actual integer, add them with ordinary arithmetic, then convert the sum back into a reversed-digit linked list.
class ListNode {
var val: Int
var next: ListNode?
init(_ val: Int) { self.val = val }
}
func addTwoNumbersBruteForce(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
func toInt(_ node: ListNode?) -> Int {
var digits: [Int] = []
var curr = node
while let n = curr {
digits.append(n.val)
curr = n.next
}
var number = 0
for digit in digits.reversed() {
number = number * 10 + digit
}
return number
}
let sum = toInt(l1) + toInt(l2)
if sum == 0 {
return ListNode(0)
}
var remaining = sum
let dummy = ListNode(0)
var tail = dummy
while remaining > 0 {
tail.next = ListNode(remaining % 10)
tail = tail.next!
remaining /= 10
}
return dummy.next
}
// smoke test: 342 + 465 = 807 -> [2,4,3] + [5,6,4] = [7,0,8]
let bl1 = ListNode(2); bl1.next = ListNode(4); bl1.next?.next = ListNode(3)
let bl2 = ListNode(5); bl2.next = ListNode(6); bl2.next?.next = ListNode(4)
var bfWalk: ListNode? = addTwoNumbersBruteForce(bl1, bl2)
while let n = bfWalk { print(n.val, terminator: " "); bfWalk = n.next } // 7 0 8Big-O: O(n + m) time to rebuild the integers and walk the sum back out, but relies on the sum fitting into a native Int — for lists long enough to represent numbers beyond 64-bit range, this approach silently breaks. O(n + m) extra space for the digit arrays and rebuilt integers.
Walk both lists digit-by-digit simultaneously, tracking a single carry, without ever materializing the full numbers.
func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
let dummy = ListNode(0)
var tail = dummy
var p1 = l1
var p2 = l2
var carry = 0
while p1 != nil || p2 != nil || carry != 0 {
let sum = (p1?.val ?? 0) + (p2?.val ?? 0) + carry
carry = sum / 10
tail.next = ListNode(sum % 10)
tail = tail.next!
p1 = p1?.next
p2 = p2?.next
}
return dummy.next
}
// smoke test: 342 + 465 = 807 -> [2,4,3] + [5,6,4] = [7,0,8]
let l1 = ListNode(2); l1.next = ListNode(4); l1.next?.next = ListNode(3)
let l2 = ListNode(5); l2.next = ListNode(6); l2.next?.next = ListNode(4)
var walk: ListNode? = addTwoNumbers(l1, l2)
while let n = walk { print(n.val, terminator: " "); walk = n.next } // 7 0 8
// smoke test: 99 + 1 = 100 -> [9,9] + [1] = [0,0,1] (trailing carry creates a new digit)
let a = ListNode(9); a.next = ListNode(9)
let b = ListNode(1)
var walk2: ListNode? = addTwoNumbers(a, b)
while let n = walk2 { print(n.val, terminator: " "); walk2 = n.next } // 0 0 1Big-O: O(max(n, m)) time — one pass across the longer list, O(1) work per node. O(1) extra space beyond the output list.
Converting to real integers first is exactly the work the reversed-digit representation was designed to let you skip — the digits are already stored least-significant-first, which is the order column addition naturally proceeds in, so there's never a reason to reconstruct the whole number. The carry is the only piece of state that needs to survive from one digit position to the next, and it's always a single value (0 or 1 for base-10 addition), so tracking it directly and emitting one result digit per step does the entire job in one pass with O(1) extra memory — and, unlike the brute force, never risks overflowing a fixed-width integer type no matter how long the lists are.
- Linked Lists — the underlying data structure; building the result list node-by-node with a dummy head and tail pointer is the standard construction pattern.
- Two Pointers — walking both lists simultaneously while carrying a small piece of state (the carry) between steps is Two Pointers applied to combining two sequences rather than comparing or merging them by order.
- Big-O Notation — for why avoiding integer reconstruction also avoids the brute force's hidden overflow risk on long inputs.
Add Two Numbers is grade-school column addition where the digits arrive ones-place-first — walk both lists together, carry the overflow, done in one pass.
Trace the optimal algorithm on l1 = [9, 9] and l2 = [1] (representing 99 + 1 = 100). Show the value of carry and the digit emitted at each iteration, and explain why the loop condition includes || carry != 0 even after both p1 and p2 have become nil.
⬅️ Previous: Copy List with Random Pointer · Next: Linked List Cycle ➡️