Pattern 2: Fast & Slow Pointers

Deep Dive: Why the Tortoise Catches the Hare

Cycle Detection Step by Step

List: 1 -> 2 -> 3 -> 4 -> 5 -> 3 (back to node 3)

Step  Slow  Fast
  0    1     1
  1    2     3
  2    3     5
  3    4     3    (fast loops back)
  4    5     5    MEET! -> cycle exists

Why they must meet: Once both are in the cycle (length C), the gap between them shrinks by 1 each step (fast gains 1, but they are in a loop). After at most C steps, gap = 0.

Finding the Cycle START (Floyd's Phase 2)

After they meet, reset one pointer to head. Move both at speed 1. They meet at the cycle start:

Reset slow to head: slow=1, fast=5 (still in cycle)
  slow=1 fast=3  ->  slow=2 fast=4  ->  slow=3 fast=5
  slow=3 fast=3  MEET at node 3 -> cycle starts here!

Math: Distance from head to cycle start = distance from meeting point to cycle start (going around the cycle).

---

Signal: Cycle detection, find middle of linked list, find duplicate in range Template: fast_slow_pointers() in templates.py

When to Use

• Linked list cycle detection
• Find the START of a cycle (Floyd's algorithm)
• Find middle node (slow at mid when fast at end)
• Detect duplicate number in [1,n] range (treat as LL cycle)

Re-solve from Phase 1-2 (TIMED)

Problem	Source	Target Time	Done?
Linked List Cycle	Phase 1.5	10 min	[ ]
Middle of the Linked List	LeetCode #876	10 min	[ ]

New Practice Problems

Add problems to solutions/ and enrich as needed.

---

First-time Recognition Signals

When you read a brand-new problem statement, this pattern is the right tool if you see:

• "Linked list — does it have a cycle? Where does it start?" — Floyd's tortoise-and-hare is the textbook tool, O(1) extra space.
• "Find the middle of a linked list in one pass" — slow lands on the middle exactly when fast hits the end.
• "Find the duplicate in an array of size n+1 with values in [1, n]" — re-interpret each value as a next pointer; the duplicate forces a cycle.
• "Happy number / sequence defined by x = f(x)" where you must detect a repeat without extra space — same cycle-detection trick on a functional sequence.
• "Determine if a linked list is a palindrome" — slow/fast to find the midpoint, then reverse the second half.

Anti-signals (looks like this pattern, isn't)

• "Kth node from the end of a linked list" — sounds similar but is best done with a fixed-gap two-pointer (both at speed 1, k apart), not slow/fast at different speeds.
• "Detect a cycle in a general directed graph" — fast/slow only works on functional graphs (out-degree exactly 1). Use DFS coloring or Union-Find for arbitrary graphs.
• "Find any duplicate in an unsorted array" with no [1, n] range guarantee — HashSet is simpler; Floyd's needs the index-as-pointer trick to apply.