Linked List Cycle Detection - Floyd's Fast & Slow Pointer Complete Guide

The Fast and Slow Pointer technique (also known as Floyd’s Tortoise and Hare) is one of the most elegant algorithms in computer science. It solves linked list cycle problems in O(1) space - a feat that seems almost magical until you understand the math behind it.

Why Interviewers Love This Algorithm

1. Tests mathematical reasoning - The proof of why it works separates good candidates from great ones
2. O(1) space constraint - HashSet solutions are “too easy”; interviewers want to see Floyd’s algorithm
3. Multiple variations - Detect cycle, find start, find duplicate number
4. Clean code - The implementation is simple, but the insight is deep

Core Intuition: The Tortoise and Hare

Imagine a circular race track. A tortoise (🐢) moves 1 step at a time, while a hare (🐇) moves 2 steps. If the track has a loop, the faster hare will eventually “lap” the slower tortoise and they’ll meet.

Linear part:    H ─── E ─── A ─── D
                              ↓
Cycle:                        ┌───────┐
                              │       │
                              C ←── Y │
                              │       │
                              └── L ──┘

Key insight: If there’s a cycle, the fast pointer will always catch up to the slow pointer. They must meet inside the cycle.

---

Interactive Visualizer

Walk through the algorithm step by step. Watch how the slow (🐢) and fast (🐇) pointers move, meet at the cycle, and then find the cycle’s starting point:

Initializing...

---

Part 1: Detecting a Cycle (LeetCode 141)

Problem: Linked List Cycle (LC 141)

Problem: Given head, determine if the linked list has a cycle.

Algorithm

1. Initialize two pointers: slow = head, fast = head
2. Move slow by 1 step, fast by 2 steps each iteration
3. If fast reaches null, no cycle exists
4. If slow === fast, a cycle exists

Code Template

JavaPythonJavaScript

Loading...

Why It Works

Theorem: If there’s a cycle, the fast pointer will eventually meet the slow pointer.

Proof:

• Once both pointers are in the cycle, consider their relative positions
• Each step, the gap between fast and slow decreases by 1 (fast gains 2, slow gains 1, net = 1)
• Eventually the gap becomes 0, and they meet

Step 0:  slow at position 0, fast at position 0
Step 1:  slow at position 1, fast at position 2  → gap = 1
Step 2:  slow at position 2, fast at position 4  → gap = 2
...
Once in cycle: gap decreases by 1 each step until they meet

---

Part 2: Finding the Cycle Start (LeetCode 142)

Problem: Linked List Cycle II (LC 142)

Problem: Find the node where the cycle begins. Return null if no cycle.

This is where the algorithm becomes truly beautiful. After finding the meeting point, we can find the cycle’s start with a simple trick.

The Two-Phase Algorithm

Phase 1: Find meeting point (same as cycle detection) Phase 2: Reset one pointer to head, move both by 1 step until they meet

Code Template

JavaPythonJavaScript

Loading...

---

Mathematical Proof: Why Phase 2 Works

This is the part that impresses interviewers. Let’s prove why resetting one pointer to head and moving both at the same speed finds the cycle start.

Setup

The Math

When slow and fast meet:

• Slow traveled: $F + a$ (just reached the meeting point)
• Fast traveled: $F + a + nC$ (went around the cycle $n$ times, $n \geq 1$)

Since fast moves twice as fast: $2(F + a) = F + a + nC$

Simplifying: $F + a = nC$

Therefore: $F = nC - a = (n-1)C + (C - a)$

What This Means

$F = (n-1)C + (C - a)$ tells us:

• $(C - a)$ is the distance from Meeting Point to Cycle Start (going forward in the cycle)
• $(n-1)C$ represents full cycle loops

Key Insight: Starting from Head and Meeting Point simultaneously, moving 1 step at a time:

• From Head: travels distance $F$ to reach Cycle Start
• From Meeting Point: travels $(C - a) + (n-1)C = F$ to reach Cycle Start

They meet exactly at the Cycle Start!

Visual Walkthrough

---

Part 3: Find the Duplicate Number (LeetCode 287)

Problem: Find the Duplicate Number (LC 287)

Problem: Given an array of $n+1$ integers where each integer is in $[1, n]$, find the duplicate. You must use O(1) extra space.

The Insight: Array as Linked List

Treat the array as a linked list where:

• Index $i$ points to index $nums[i]$
• The duplicate number creates a cycle!

Example: nums = [1, 3, 4, 2, 2]

Index:   0 → 1 → 3 → 2 → 4
               ↓       ↓
Value:   1   3   4   2   2
                       ↑
                  Duplicate creates cycle!

0 → nums[0] = 1
1 → nums[1] = 3
3 → nums[3] = 2
2 → nums[2] = 4
4 → nums[4] = 2  ← Back to index 2!

The cycle: 2 → 4 → 2 → 4 → ...
Cycle start = 2 (the duplicate number!)

Code Template

JavaPythonJavaScript

Loading...

Why This Works

1. Since values are in $[1, n]$ and we start from index 0, we never get stuck at index 0
2. The duplicate value means two indices point to the same location → cycle!
3. The cycle’s starting point is the duplicate number

---

Time & Space Complexity

Problem	Time	Space
Detect Cycle (LC 141)	O(n)	O(1)
Find Cycle Start (LC 142)	O(n)	O(1)
Find Duplicate (LC 287)	O(n)	O(1)

Why O(n) time?

• Phase 1: At most 2n steps (fast pointer traverses at most twice)
• Phase 2: At most n steps (from head to cycle start)

Why O(1) space?

• Only two pointers, no matter the input size

---

🔥 Why Must Fast Move Exactly 2 Steps? (Critical Proof)

This is a frequently asked follow-up question in interviews. Many people think fast can move 3 or 4 steps, but only 2 steps guarantees 100% meeting!

Core Insight: Relative Speed Determines Everything

Fast Steps	Slow Steps	Relative Speed	Distance Change
2	1	1	d → d-1 → d-2 → … → 1 → 0 ✓
3	1	2	d → d-2 → d-4 → … (may skip 0)
4	1	3	d → d-3 → d-6 → … (may skip 0)

Key: Only when relative speed = 1, distance decreases by 1 each time, must pass through 0 (meeting point).

❌ Counter-Example: Fast Moving 3 Steps Never Catches Up!

Mathematical Proof

Let cycle length be $C$, and distance between fast and slow be $d$.

Relative speed = 1 (fast moves 2 steps): $d \to d-1 \to d-2 \to \cdots \to 1 \to 0 \checkmark$

Every integer is visited, must pass through 0 (meeting point).

Relative speed = 2 (fast moves 3 steps): $d \to d-2 \to d-4 \to \cdots$

Only visits even or only odd numbers. If $d$ is odd: $d \to d-2 \to \cdots \to 1 \to (1-2+C) = C-1 \to C-3 \to \cdots$

When $C$ is even, distance cycles between odd numbers, forever skipping 0!

General Rule

If fast moves $k$ steps, relative speed $v = k - 1$.

Meeting condition: $\gcd(v, C)$ must divide initial distance $d$

Relative Speed $v$	$\gcd(v, C)$	Guaranteed Meeting?
$v = 1$	$\gcd(1, C) = 1$	Always divides any $d$ ✓
$v = 2$	$1$ or $2$	When $C$ even & $d$ odd: NO ❌
$v = 3$	$1$ or $3$	May fail ❌

Visual Understanding

Relative speed = 1 (2 steps):
  ●───●───●───●───●───●───●───●
  d   d-1  d-2  d-3  ...  1    0 ✓
  Every integer is visited, must reach 0

Relative speed = 2 (3 steps):
  ●───○───●───○───●───○───●───○
  d      d-2      d-4      ...
  Only visits even or odd, may forever skip 0!

Relative speed = 3 (4 steps):
  ●───○───○───●───○───○───●───○
  d          d-3          d-6
  Visits 1 in every 3 numbers, likely skips 0!

---

Common Interview Mistakes

Mistake 1: Wrong Initialization

// ❌ WRONG - Will miss cycles at head
let slow = head;
let fast = head.next;  // Don't do this!

// ✅ CORRECT
let slow = head;
let fast = head;

Mistake 2: Forgetting Null Checks

// ❌ WRONG - Will crash on short lists
while (fast.next) {
  fast = fast.next.next;  // Might be null!
}

// ✅ CORRECT
while (fast && fast.next) {
  fast = fast.next.next;
}

Mistake 3: Wrong Phase 2 Speed

// ❌ WRONG - Fast still moves 2 steps
while (slow !== fast) {
  slow = slow.next;
  fast = fast.next.next;  // Should be 1 step!
}

// ✅ CORRECT
while (slow !== fast) {
  slow = slow.next;
  fast = fast.next;  // BOTH move 1 step
}

---

Edge Cases

1. Empty list: head === null → No cycle
2. Single node without cycle: Only head, head.next === null → No cycle
3. Single node with cycle: head.next === head → Cycle exists, start = head
4. Cycle at head: The first node is the cycle start
5. Very long tail, small cycle: Works the same, just takes longer

---

Related Problems

Problem	Difficulty	Key Insight
141. Linked List Cycle	Easy	Basic detection
142. Linked List Cycle II	Medium	Find cycle start
287. Find Duplicate	Medium	Array as linked list
202. Happy Number	Easy	Cycle in number sequence
876. Middle of Linked List	Easy	When fast reaches end, slow is at middle

---

Interview Tips

How to Explain to Interviewer

1. Start with intuition: “Imagine a race track with a loop…”
2. Explain Phase 1: “The fast pointer will catch up to slow if there’s a cycle”
3. Prove Phase 2: “The distance from head to cycle start equals meeting point to cycle start”
4. Write clean code: Start with null checks, then the two-phase algorithm

Common Follow-up Questions

Q: Can you prove Phase 2 mathematically? A: Yes! Use the equation $2(F + a) = F + a + nC$, leading to $F = nC - a$.

Q: What if there are multiple duplicates? A: Floyd’s algorithm finds one cycle. For multiple duplicates, you’d need a different approach.

Q: Can this work with fast moving 3 steps? A: No! With 3 steps, relative speed = 2. When cycle length is even and initial distance is odd, fast and slow will never meet. See the proof and counter-example in “Why Must Fast Move Exactly 2 Steps” section above.

---

Summary

Floyd’s Cycle Detection is a must-know algorithm for interviews:

1. Detect Cycle: Slow and fast pointers; if they meet, cycle exists
2. Find Cycle Start: After meeting, reset one pointer to head, move both by 1 step
3. The Math: $F = nC - a$ proves why Phase 2 works
4. Applications: Linked lists, finding duplicates, happy numbers

Master this algorithm, and you’ll handle an entire category of interview questions with confidence!