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 List
slow 1 step, fast 2 stepseasy
2.Linked List Cycle
Floyd Cycle Detection (slow == fast)easy
3.Linked List Cycle II
Meet once -> reset one to head -> move 1 stepmedium
4.Happy Number
Fast/slow on sum of squared digitseasy
5.Palindrome Linked List
Find mid with fast/slow + reverse second halfeasy
6.Reorder List
Find mid + reverse second half + interleavemedium
7.Find the Duplicate Number
Array as implicit linked list (nums[i] pointer)medium
8.Circular Array Loop
Fast/slow on array index jumpsmedium
9.Split Linked List in Parts
Length count + fast/slow split pointsmedium
10.Maximum Twin Sum of a Linked List
Find mid with fast/slow + reverse second halfmedium

Also Important

7 more questions worth practicing.

11.Remove Nth Node From End of List
Two pointers with gap Nmedium
12.Delete the Middle Node of a Linked List
Slow + Fast with prev pointermedium
13.Sort List
Merge sort (find mid with slow/fast)medium
14.Rotate List
Fast/slow or ring connectionmedium
15.Intersection of Two Linked Lists
Two pointers equalizing path lengtheasy
16.Find Middle of Circular Linked List
Cycle fast/slow boundary terminationmedium
17.Cycle Detection Variants
Functional 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."

Visual Memory Rule

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

1. Nil Pointer Panic

Doing fast = fast.Next.Next without checking fast != nil && fast.Next != nil first.

2. Comparing Node Values

Comparing slow.Val == fast.Val instead of node references slow == fast. Different nodes can have identical values!

3. Resetting Wrong Speed on Cycle Start

After slow and fast meet, reset one pointer to head, but make sure BOTH pointers now move at 1 step at a time!

4. Overusing Fast/Slow

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.Next and fast = fast.Next.Next.
Rule 2: Always check fast != nil && fast.Next != nil before accessing fast.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."