-
Notifications
You must be signed in to change notification settings - Fork 0
016 — Fast and Slow Pointers
Two Pointers converged from opposite ends. Sliding Window moved together in lockstep. Fast and Slow Pointers is the third shape: both pointers start at the same place and move in the same direction, but at different speeds — and that speed difference alone is enough to detect cycles and find midpoints without ever needing to know the structure's total length in advance.
The Linked Lists chapter covered the data structure itself — nodes linked one-way by .next, with no index to jump to and no length known up front. This chapter is about recognizing when to run two pointers through that structure at different speeds: cycle detection is the canonical case, since a linked list is exactly the kind of structure where "does this loop back on itself?" can only be answered by walking it.
Picture two runners on a circular track — one runs at normal pace, the other at double speed. If the track is actually a straight line with a finish tape at the end, the fast runner just gets there first, easy. But if the track secretly loops back on itself somewhere, the fast runner never finds a finish line — instead, having gone around twice as fast, they eventually catch up and lap the slow runner from behind. That catch-up moment is unmistakable proof the track loops. No mental map, no counting laps, no marking the ground — just: "did the fast one ever run into the slow one again?"
This is the whole trick: you rarely know in advance whether a structure (usually a linked list) loops back on itself or how long it is. Racing two pointers at different speeds through it answers both questions cheaply — a meeting means a cycle, and the relative distance covered pins down the midpoint — all using only O(1) extra memory.
Fast and Slow Pointers (also called "the tortoise and the hare") is a strong reach when the problem statement mentions:
-
"Cycle" or "loop" — "detect if a linked list has a cycle," "find where the cycle begins" — the fast pointer moving 2 steps to the slow pointer's 1 step is the single most reliable way to detect a loop in
O(1)space, without a hash set of visited nodes. -
"Middle of a linked list" — since you can't jump to
length / 2without a length pass first, running a fast pointer at 2x speed means when it hits the end, the slow pointer is sitting exactly at the middle. -
"Duplicate number in an array of
1...n" — a deceptively array-shaped problem that's secretly a linked-list-cycle problem in disguise: treating each value as "the index to go to next" turns the array into an implicit linked list, and a duplicate value guarantees two indices point to the same next stop, which creates a cycle. - Palindrome linked list, or any check that needs the list's midpoint as a stepping stone to another operation (like reversing the second half) — fast/slow finds the midpoint in one pass instead of two.
The unifying tell: a linked structure (or an array masquerading as one via index-as-pointer) where you need cycle detection or a midpoint, and you want to avoid the O(n) extra space of tracking every node you've visited.
A linked list with a cycle — slow moves 1 node per step, fast moves 2:
1 → 2 → 3 → 4 → 5
↑ ↓
8 ← 7 ← 6
step 0: slow=1, fast=1
step 1: slow=2, fast=3
step 2: slow=3, fast=5
step 3: slow=4, fast=7
step 4: slow=5, fast=4 ← fast wrapped around the loop
step 5: slow=6, fast=6 ← MEETING POINT — cycle confirmed!
Why they're guaranteed to meet: once both pointers are inside the loop,
fast gains exactly 1 node on slow every step (it moves 2, slow moves 1).
A loop is finite, so "gaining 1 node per step" must eventually close the
gap to exactly 0 — they can't skip past each other in a single-lane loop.
class ListNode {
var val: Int
var next: ListNode?
init(_ val: Int) { self.val = val }
}
func fastSlowTemplate(_ head: ListNode?) -> Bool {
var slow = head
var fast = head
while fast != nil && fast?.next != nil {
slow = slow?.next // slow moves 1 step
fast = fast?.next?.next // fast moves 2 steps
// 🔧 Fill in: what happens when they meet? (cycle found, etc.)
if slow === fast {
return true
}
}
// 🔧 fast reached the end without meeting slow — no cycle,
// OR: slow is now sitting at the midpoint (if that's what you needed).
return false
}The skeleton never changes: two pointers start at head, the loop guard checks fast and fast?.next are both non-nil (so fast?.next?.next never crashes), slow advances by 1, fast advances by 2, and something is checked or recorded every iteration. What differs per-problem is why you're racing them — cycle detection compares identity (===) each step; finding a midpoint just reads slow's final position once the loop guard fails.
Linked List Cycle II — given the head of a linked list, return the node where the cycle begins, or nil if there's no cycle.
func detectCycle(_ head: ListNode?) -> ListNode? {
var slow = head
var fast = head
// Phase 1: race until they meet, or fast falls off the end.
while fast != nil && fast?.next != nil {
slow = slow?.next
fast = fast?.next?.next
if slow === fast {
// Phase 2: reset one pointer to head, advance BOTH one step at a time.
// They're mathematically guaranteed to meet exactly at the cycle's start.
var pointer1 = head
var pointer2 = slow
while pointer1 !== pointer2 {
pointer1 = pointer1?.next
pointer2 = pointer2?.next
}
return pointer1
}
}
return nil // fast reached the end — no cycle exists
}
// smoke test: build 1 -> 2 -> 3 -> 4 -> 5 -> back to 3
let n1 = ListNode(1), n2 = ListNode(2), n3 = ListNode(3), n4 = ListNode(4), n5 = ListNode(5)
n1.next = n2; n2.next = n3; n3.next = n4; n4.next = n5; n5.next = n3
print(detectCycle(n1)?.val ?? -1) // 3
let a1 = ListNode(1), a2 = ListNode(2)
a1.next = a2 // no cycle
print(detectCycle(a1)?.val ?? -1) // -1Mapped onto the template: Phase 1 is exactly fastSlowTemplate's loop, checking slow === fast each step. The problem needs more than a yes/no answer though, so Phase 2 extends the pattern — a well-known bit of pointer arithmetic proves that resetting one pointer to head and advancing both one step at a time makes them meet exactly at the cycle's entrance. The core race is unchanged; only what happens after the meeting is problem-specific.
Fast and Slow Pointers is two runners on a track at different speeds — if the track loops, the fast one always laps the slow one, and that catch-up moment proves the loop exists without ever mapping the track.
A problem gives you an array nums of length n + 1 where every value is between 1 and n inclusive, and guarantees at least one value repeats — find the duplicate, using O(1) extra space. Explain how to reframe this array as an implicit linked list so that Fast and Slow Pointers applies, and identify what plays the role of a "node" and what plays the role of "next."