Skip to content

065 — Reverse Linked List

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 2 revisions

65 — Reverse Linked List

LeetCode 206 · Easy. Given the head of a singly linked list, reverse the list, and return the reversed list's head.

🍽️ Intuition

Picture a line of train cars, each one coupled facing forward — car 1 points to car 2, car 2 points to car 3, and so on. Reversing the train means walking down the line and re-coupling every car to face backward instead, one coupling at a time. The catch: the moment you uncouple a car from the one ahead of it to flip it around, you'd lose your way back to the rest of the train — unless you're holding onto three things at once: the car you just flipped (behind you), the car you're flipping right now, and the car you haven't touched yet (ahead of you). Three hands, one pass, and the whole train ends up facing the other way.

🚩 Pattern-Recognition Cue

"Reverse" plus "linked list" is about as direct a cue as it gets. There's no searching, no comparing values — just a structural rewiring of every next pointer. Whenever a problem asks you to flip the direction of a chain of nodes (here, or as a sub-step inside a bigger problem like Reorder List), reach for the three-pointer walk below.

🐢 Brute Force

Walk the list once to collect every node into an array (extra O(n) space), then relink each node's next pointer by walking the array back to front.

class ListNode {
    var val: Int
    var next: ListNode?
    init(_ val: Int) { self.val = val }
}

func reverseListBruteForce(_ head: ListNode?) -> ListNode? {
    var nodes: [ListNode] = []
    var current = head
    while let node = current {
        nodes.append(node)
        current = node.next
    }
    guard !nodes.isEmpty else { return nil }

    for i in stride(from: nodes.count - 1, to: 0, by: -1) {
        nodes[i].next = nodes[i - 1]
    }
    nodes[0].next = nil
    return nodes[nodes.count - 1]
}

// smoke test: 1 -> 2 -> 3 -> 4 -> 5
let bfHead = ListNode(1)
bfHead.next = ListNode(2)
bfHead.next?.next = ListNode(3)
bfHead.next?.next?.next = ListNode(4)
bfHead.next?.next?.next?.next = ListNode(5)
var bfWalk: ListNode? = reverseListBruteForce(bfHead)
while let n = bfWalk { print(n.val, terminator: " "); bfWalk = n.next }   // 5 4 3 2 1

Big-O: O(n) time — one pass to collect, one pass to relink. O(n) extra space for the array of node references, on top of the list itself.

🚀 Optimal

Walk the list exactly once with three pointers — prev, curr, and a temporary next — flipping each next pointer as you go.

func reverseList(_ head: ListNode?) -> ListNode? {
    var prev: ListNode? = nil
    var curr = head

    while curr != nil {
        let nextTemp = curr?.next   // save what's ahead before we overwrite curr.next
        curr?.next = prev           // flip this node's pointer backward
        prev = curr                 // advance prev
        curr = nextTemp             // advance curr to the node we saved
    }

    return prev   // when curr falls off the end, prev is sitting on the new head
}

// smoke test: 1 -> 2 -> 3 -> nil
let n1 = ListNode(1); let n2 = ListNode(2); let n3 = ListNode(3)
n1.next = n2; n2.next = n3
var walk: ListNode? = reverseList(n1)
while let n = walk { print(n.val, terminator: " "); walk = n.next }   // 3 2 1

print(reverseList(nil) == nil)   // true — empty list stays nil

Big-O: O(n) time — a single pass touches each node once. O(1) extra space — only three pointer variables, regardless of list length.

🔑 The Key Insight

The whole difficulty of reversing a linked list in place is that overwriting curr.next destroys your only path to the rest of the list — once you've flipped a node's pointer backward, you've cut the thread forward. The fix is to never let go of "what's ahead" until you've saved it: nextTemp captures the node you still need to visit before curr.next gets clobbered. That's the entire trick that collapses the brute force's extra array (which exists purely to remember "what came before/after" once pointers are gone) down to three plain variables and O(1) space — you don't need to remember the whole train, just the one car on either side of the one you're currently flipping.

🔗 Related Chapters

  • Linked Lists — the underlying data structure; this problem is pure pointer rewiring with no other structure involved.
  • Two Pointers — the prev/curr/next three-pointer walk is a direct application of the Two Pointers pattern to a linked structure rather than an array. Two Pointers isn't just an array trick — here the "two pointers" are prev and curr marching in lockstep through the list, one step apart, exactly like two indices marching through an array.
  • Big-O Notation — for the O(n) extra space vs. O(1) extra space comparison above.

🧸 Memory Sentence

Reverse Linked List is re-coupling a train car by car — hold the car behind, the car you're flipping, and the car ahead in three hands so the line never breaks.

✅ Check Your Understanding

Trace the optimal algorithm on 1 -> 2 -> 3 -> nil. Write out the values of prev, curr, and nextTemp at the start of each loop iteration, and explain why the function returns prev instead of curr once the loop ends.

⬅️ Previous: Median of Two Sorted Arrays · Next: Merge Two Sorted Lists ➡️

Clone this wiki locally