🐢🐇

Fast / Slow Pointers — Floyd's Cycle Detection

Two pointers at different speeds — slow moves 1 step, fast moves 2 steps — to detect cycles, find midpoints, and locate cycle entry nodes in O(1) space.

Linked List Floyd's Algorithm Cycle Detection Find Middle Time O(n) Space O(1)

📋 When to Use

Detect if a linked list has a cycle
Find the cycle entry node (where cycle begins)
Find the middle node of a linked list
Detect cycles in implicit sequences (Happy Number, Duplicate)
Need O(1) space — cannot use a HashSet for visited nodes
Check if a linked list is a palindrome (find mid + reverse)

💡 Key insight: if a cycle exists, fast will eventually "lap" slow and they meet inside the cycle. The meeting point math guarantees: resetting slow to head and moving both 1 step at a time leads them to the cycle start.

⚡ Complexity

Time

O(n)

Space

O(1)

Phase 1 (detect): at most O(λ + μ) steps where λ = cycle length, μ = tail length. Phase 2 (find start): at most O(μ) more steps. Total = O(n). Only two pointer variables — no extra data structures.

Math Proof Sketch

        meet point distance from start = μ (tail)

        ∴ slow(reset to head) and fast both

        reach cycle entry after μ more steps ✓

Problem Given linked list 1→2→3→4→5→(tail back to node 3), detect whether a cycle exists and find where it begins (LC #141). Fast pointer moves 2 steps, slow moves 1 — they meet inside the cycle. Reset slow to head, advance both 1 step at a time to find the entry node.
Input: [1,2,3,4,5], tail connects to node 3 · Answer: cycle detected, entry = node 3 · middle of [1,2,3,4,5] = node 3 (LC #876)

Step 1 / —

🏃 Traversing

💥 Cycle Detected

🎯 Find Start

✅ Done

slow 🐢 moves 1 step

fast 🐇 moves 2 steps

yellow = meeting point

bright green = cycle start

🐢 slow: 1

🐇 fast: 1

🔄 steps: 0

Status: Init

Click ▶ Play or Next ▶ to start the animation

Java Pattern TemplateJAVA 8

// Fast / Slow Pointers — Floyd's Cycle Detection
ListNode slow = head, fast = head;

// Phase 1: Detect cycle
while (fast != null && fast.next != null) {
    slow = slow.next;          // move 1 step  🐢
    fast = fast.next.next;     // move 2 steps 🐇
    if (slow == fast) break;   // cycle found 💥
}
if (fast == null || fast.next == null) return null; // no cycle

// Phase 2: Find cycle start 🎯
slow = head;                   // reset slow to head
while (slow != fast) {
    slow = slow.next;          // both move 1 step
    fast = fast.next;
}
return slow;                   // cycle start node

// ─────────────────────────────────────────
// Find Middle (no cycle) — LC #876
while (fast != null && fast.next != null) {
    slow = slow.next;          // slow moves 1 step
    fast = fast.next.next;     // fast moves 2 steps
}
return slow;                   // middle node 🎯

🎯 Practice Problems

#141Linked List Cycle — detect if cycle existsEasy #142Linked List Cycle II — find the cycle start nodeMedium #876Middle of the Linked ListEasy #202Happy Number — cycle in implicit digit-sum sequenceEasy #287Find the Duplicate Number — Floyd's on array indicesMedium #234Palindrome Linked List — find mid, reverse second halfEasy