Pattern #14
Fast & Slow Pointers
Important interview questions, thinking patterns, Floyd's cycle detection, and rules for solving Fast & Slow pointer problems in Go.
Must Solve
10 core questions โ solve these first.
- 1.Middle of the Linked Listslow 1 step, fast 2 stepseasy
- 2.Linked List CycleFloyd Cycle Detection (slow == fast)easy
- 3.Linked List Cycle IIMeet once -> reset one to head -> move 1 stepmedium
- 4.Happy NumberFast/slow on sum of squared digitseasy
- 5.Palindrome Linked ListFind mid with fast/slow + reverse second halfeasy
- 6.Reorder ListFind mid + reverse second half + interleavemedium
- 7.Find the Duplicate NumberArray as implicit linked list (nums[i] pointer)medium
- 8.Circular Array LoopFast/slow on array index jumpsmedium
- 9.Split Linked List in PartsLength count + fast/slow split pointsmedium
- 10.Maximum Twin Sum of a Linked ListFind mid with fast/slow + reverse second halfmedium
Also Important
7 more questions worth practicing.
- 11.Remove Nth Node From End of ListTwo pointers with gap Nmedium
- 12.Delete the Middle Node of a Linked ListSlow + Fast with prev pointermedium
- 13.Sort ListMerge sort (find mid with slow/fast)medium
- 14.Rotate ListFast/slow or ring connectionmedium
- 15.Intersection of Two Linked ListsTwo pointers equalizing path lengtheasy
- 16.Find Middle of Circular Linked ListCycle fast/slow boundary terminationmedium
- 17.Cycle Detection VariantsFunctional graph cycle detectionmedium
How to Think
- Need middle?slow = 1 step, fast = 2 steps
- Need detect cycle?slow + fast (if they meet: cycle exists)
- Need cycle starting point?Meet once -> reset one to head -> move both 1 step
- Need split list into halves?slow + fast (slow reaches middle)
- Need find repeated state without extra memory?Floyd's Cycle Detection
Go Templates
Find Middle of Linked List Template
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
return slow // Slow is at the middle node!Detect Cycle Template (Floyd's Algorithm)
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
return true // Cycle exists!
}
}
return false // No cycle๐ Time: O(n) | Space: O(1)
Why This Works: The Running Track Analogy
Imagine two runners on a circular track โ one running at speed 1 (slow) and another at speed 2 (fast).
No Loop โ Fast runner reaches the finish line (nil node)
Loop โ Fast runner laps the slow runner and they meet (slow == fast)๐ก Golden Rule: "Meet โ Cycle | Reach nil โ No Cycle."
Middle: Slow 1 step, Fast 2 steps โ Fast hits nil, Slow at middle
Cycle: Slow 1 step, Fast 2 steps โ Meet inside loop (O(1) space)
Cycle Start: Meet once โ reset one pointer to head โ move both 1 step๐ก Golden Rule: "If you can keep following 'next', let one pointer move twice as fast and watch what happens."
Common Interview Mistakes
Doing fast = fast.Next.Next without checking fast != nil && fast.Next != nil first.
Comparing slow.Val == fast.Val instead of node references slow == fast. Different nodes can have identical values!
After slow and fast meet, reset one pointer to head, but make sure BOTH pointers now move at 1 step at a time!
Fast & Slow is designed for sequential state traversal (next node / next state). Don't force it into random array problems.
Interview Rules
- 1. Middle of list? โ Slow + Fast
- 2. Cycle detection? โ Slow + Fast
- 3. Cycle start? โ Meet once, reset one to head, move both 1 step
- 4. Split list? โ Slow + Fast
- 5. Repeated state sequence?โ Consider Floyd's algorithm
- 6. Slow moves โ 1 step
- 7. Fast moves โ 2 steps
- 8. Fast reaches nil โ No cycle
- 9. Slow meets Fast โ Cycle
- 10. Complexity โ
O(n) time, O(1) space
Small Rules
- Rule 1: Standard movement:
slow = slow.Nextandfast = fast.Next.Next. - Rule 2: Always check
fast != nil && fast.Next != nilbefore accessingfast.Next.Next. - Rule 3: Fast/Slow uses O(1) extra space vs O(n) space for Hash Set.
- Rule 4:Hash Set takes O(n) space while Floyd's algorithm takes O(1) space.
- Rule 5: Odd vs even list lengths affect whether slow lands on the first or second middle node.
Production Thinking
Retry / State Loops โ Detect repeated process state loops without storing state history
Workflow Cycle Detection โ Identify self-referencing tasks in pipeline graphs
Dependency Chains โ Service dependency cycle validation (A -> B -> C -> A)
Memory Advantage โ O(1) memory vs storing millions of visited states in Hash Set
Remember This
Middle โ Slow 1, Fast 2
Cycle โ If they meet
No cycle โ Fast reaches nil
Cycle start โ Meet -> Reset one to head -> Move both 1 step
Space โ O(1)๐ก Golden Rule: "If you can keep following 'next', let one pointer move twice as fast and watch what happens."