Fast and Slow Pointers: Why the Slow Pointer Always Catches the Fast Pointer in a Cycle

You've seen the code for detecting a cycle in a linked list:

def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

It works. You've tested it. But why does it work?

Why does the slow pointer always catch the fast pointer if there's a cycle? What if the fast pointer just keeps jumping over the slow pointer forever? What if they never meet?

These are the questions that separate someone who memorizes the algorithm from someone who understands it. And in interviews, understanding matters—because interviewers will ask you to explain your reasoning.

This guide will give you both the intuitive explanation and the mathematical proof of Floyd's cycle detection algorithm (also called the "tortoise and hare" algorithm).

TL;DR

• Intuition: If there's a cycle, both pointers eventually enter it. Once inside, the fast pointer "laps" the slow pointer like runners on a circular track.
• Proof: When both pointers are in the cycle, the distance between them decreases by 1 each step. Eventually, the distance becomes 0 (they meet).
• Key insight: The fast pointer doesn't "jump over" the slow pointer—it closes the gap by exactly 1 position per iteration.
• Time complexity: O(n) where n is the number of nodes
• Space complexity: O(1)

The Intuitive Explanation

The Running Track Analogy

Imagine two runners on a track:

• Slow runner (tortoise): Runs at 1 meter/second
• Fast runner (hare): Runs at 2 meters/second

Scenario 1: Straight track (no cycle)

• The fast runner reaches the end first
• They never meet
• This is like a linked list with no cycle

Scenario 2: Circular track (cycle)

• Both runners keep going in circles
• The fast runner is gaining on the slow runner
• Eventually, the fast runner "laps" the slow runner
• They meet at some point on the track

Key insight: On a circular track, a faster runner will always catch a slower runner, no matter where they start.

The Linked List Version

In a linked list with a cycle:

1. Before the cycle: Fast pointer moves ahead, slow pointer follows
2. Entering the cycle: Both pointers eventually enter the cycle (fast enters first)
3. Inside the cycle: Fast pointer is ahead, but the gap closes by 1 node per iteration
4. Meeting point: When the gap becomes 0, they meet

Visual Example

Linked list with cycle:
1 -> 2 -> 3 -> 4 -> 5
          ^         |
          |         v
          8 <- 7 <- 6

Cycle: 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 3 (repeats)

Step 0: slow=1, fast=1
Step 1: slow=2, fast=3
Step 2: slow=3, fast=5
Step 3: slow=4, fast=7
Step 4: slow=5, fast=3 (fast is now behind slow in the cycle!)
Step 5: slow=6, fast=5 (gap = 1)
Step 6: slow=7, fast=7 (MEET!)

Notice how the fast pointer, despite being "fast," ends up behind the slow pointer in the cycle, then catches up.

The Mathematical Proof

Let's prove rigorously that the slow and fast pointers must meet if there's a cycle.

Setup

Let's define:

• L = length of the non-cyclic part (before entering the cycle)
• C = length of the cycle
• k = position where slow pointer is in the cycle when fast pointer enters

Phase 1: Both Pointers Enter the Cycle

Claim: If there's a cycle, both pointers will eventually enter it.

Proof:

• The fast pointer moves 2 steps per iteration
• The slow pointer moves 1 step per iteration
• After L iterations, the slow pointer is at the cycle entrance
• After L/2 iterations (rounded up), the fast pointer has passed the cycle entrance
• Therefore, both pointers eventually enter the cycle ✓

Phase 2: Inside the Cycle

Once both pointers are in the cycle, let's analyze their positions.

Define:

• Let d = distance between slow and fast pointers (measured in nodes)
• Initially, when slow enters the cycle, fast is already somewhere in the cycle

Key observation: Each iteration:

• Slow moves 1 step forward
• Fast moves 2 steps forward
• The relative distance between them changes by: 2 - 1 = 1 step

More precisely:

• If fast is d nodes ahead of slow
• After one iteration, fast is (d - 1) mod C nodes ahead

Why d - 1?

• Fast moves 2 steps, slow moves 1 step
• The gap closes by 1 step
• We use mod C because positions wrap around in a cycle

The Convergence Proof

Claim: The distance d will eventually become 0.

Proof by iteration:

Let's say when slow enters the cycle, fast is d₀ nodes ahead (where 0 < d₀ < C).

• After 1 iteration: d₁ = (d₀ - 1) mod C
• After 2 iterations: d₂ = (d₀ - 2) mod C
• After 3 iterations: d₃ = (d₀ - 3) mod C
• ...
• After d₀ iterations: d = (d₀ - d₀) mod C = 0

Therefore, after at most C iterations, the distance becomes 0, and the pointers meet. ✓

Why Can't Fast "Jump Over" Slow?

This is a common misconception. Let's prove it can't happen.

Claim: The fast pointer cannot jump over the slow pointer without meeting.

Proof:

Suppose at some iteration:

• Slow is at position p
• Fast is at position p - 1 (one position behind)

After one iteration:

• Slow moves to position p + 1
• Fast moves to position p - 1 + 2 = p + 1

They meet at position p + 1!

The key insight: because fast moves exactly 2 steps and slow moves exactly 1 step, the gap closes by exactly 1 each time. When the gap is 1, they meet on the next iteration. Fast can never "skip over" slow.

Formal Proof Using Modular Arithmetic

For those who want the rigorous version:

Let:

• s(t) = position of slow pointer at time t
• f(t) = position of fast pointer at time t
• Both positions measured as distance from cycle entrance

We have:

• s(t) = t (mod C)
• f(t) = 2t (mod C)

They meet when s(t) = f(t):

• t ≡ 2t (mod C)
• 0 ≡ t (mod C)
• t = kC for some integer k

Therefore, they meet after exactly C iterations (or a multiple of C if fast was already ahead). ✓

Edge Cases and Special Scenarios

Edge Case 1: No Cycle

# List: 1 -> 2 -> 3 -> None

slow = fast = head  # Both at 1
# Iteration 1: slow=2, fast=3
# Iteration 2: slow=3, fast=None (fast.next is None)
# Loop terminates, return False

Why it works: The fast pointer reaches the end (None) before they can meet.

Edge Case 2: Single Node Cycle

# List: 1 -> 1 (points to itself)

slow = fast = head  # Both at 1
# Iteration 1: slow=1, fast=1 (fast.next.next = 1)
# They meet immediately!

Why it works: In a cycle of length 1, they meet on the first iteration.

Edge Case 3: Two Node Cycle

# List: 1 -> 2 -> 1 (cycle between 1 and 2)

slow = fast = head  # Both at 1
# Iteration 1: slow=2, fast=2
# They meet!

Why it works: In a cycle of length 2, fast "laps" slow immediately.

Edge Case 4: Empty List or Single Node (No Cycle)

# List: None or 1 -> None

# The condition "while fast and fast.next" handles this:
# - If head is None, fast is None, loop doesn't run
# - If only one node, fast.next is None, loop doesn't run

Why This Algorithm Is Brilliant

Floyd's cycle detection has several elegant properties:

1. O(1) Space Complexity

Unlike using a hash set to track visited nodes (O(n) space), this uses only two pointers.

# Hash set approach (O(n) space)
def hasCycle(head):
    visited = set()
    current = head
    while current:
        if current in visited:
            return True
        visited.add(current)
        current = current.next
    return False

# Floyd's approach (O(1) space)
def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

2. O(n) Time Complexity

Even though it seems like the fast pointer might loop many times, the algorithm is still O(n):

• Non-cyclic part: Fast pointer traverses L nodes in L/2 iterations
• Cyclic part: At most C iterations to meet (where C ≤ n)
• Total: O(L + C) = O(n)

3. Elegant Simplicity

The code is remarkably simple—just 6 lines—yet solves a non-trivial problem.

Finding the Cycle Start (Bonus)

Once you've detected a cycle, you can find where it starts:

def detectCycle(head):
    # Phase 1: Detect cycle
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None  # No cycle
    
    # Phase 2: Find cycle start
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    
    return slow  # This is the cycle start

Why this works:

When they meet inside the cycle:

• Slow has traveled: L + a (where a is distance into cycle)
• Fast has traveled: L + a + nC (where n is number of complete cycles fast made)

Since fast travels twice as fast: 2(L + a) = L + a + nC

Solving: L + a = nC, so L = nC - a

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

Common Misconceptions

Misconception 1: "Fast might jump over slow"

Reality: The gap closes by exactly 1 each iteration. When gap = 1, they meet next iteration.

Misconception 2: "This only works for certain cycle lengths"

Reality: The proof works for any cycle length C ≥ 1.

Misconception 3: "They might meet outside the cycle"

Reality: They can only meet inside the cycle, because that's where both pointers loop.

Misconception 4: "Fast pointer might loop forever without catching slow"

Reality: The gap decreases by 1 each iteration, so they must meet within C iterations.

Implementation Variants

Variant 1: Different Speeds

What if fast moves 3 steps instead of 2?

def hasCycle(head):
    slow = fast = head
    while fast and fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next.next  # 3 steps
        if slow == fast:
            return True
    return False

Does it work? Yes, but it's less efficient. The gap closes by 2 each iteration, so they might miss each other if the cycle length is even. The 2x speed is optimal.

Variant 2: Starting Positions

What if they start at different positions?

def hasCycle(head):
    if not head or not head.next:
        return False
    slow = head
    fast = head.next  # Start one ahead
    while fast and fast.next:
        if slow == fast:
            return True
        slow = slow.next
        fast = fast.next.next
    return False

Does it work? Yes, but the standard version (both starting at head) is cleaner.

Practice Problems

To master this technique:

1. Linked List Cycle (LeetCode #141) - basic cycle detection
2. Linked List Cycle II (LeetCode #142) - find cycle start
3. Happy Number (LeetCode #202) - cycle detection in number sequences
4. Find the Duplicate Number (LeetCode #287) - array as linked list

FAQ

Q: Why does fast move 2 steps instead of 3 or more?

A: Moving 2 steps is optimal. It guarantees they meet within C iterations and has the simplest null-checking logic. Moving 3+ steps might cause them to miss each other in small cycles.

Q: What if there are multiple cycles?

A: A linked list can only have one cycle (each node has one next pointer). The algorithm will detect it.

Q: Can I use this on arrays?

A: Yes! For problems like "Find the Duplicate Number," you can treat array indices as a linked list where next[i] = nums[i].

Q: What's the worst-case time complexity?

A: O(n) where n is the number of nodes. Even if the cycle is large, fast catches slow within C iterations, and C ≤ n.

Q: Why is it called "tortoise and hare"?

A: It's named after Aesop's fable "The Tortoise and the Hare." The slow pointer is the tortoise, the fast pointer is the hare. Unlike the fable, the hare always catches the tortoise in a cycle!

Conclusion

Floyd's cycle detection algorithm is a beautiful example of how simple code can solve a complex problem with rigorous mathematical backing.

Key insights:

• Intuition: Fast runner laps slow runner on a circular track
• Proof: Gap closes by 1 each iteration, must reach 0 within C iterations
• Efficiency: O(n) time, O(1) space
• Robustness: Works for all cycle lengths, handles edge cases elegantly

Why it works:

1. Both pointers eventually enter the cycle
2. Inside the cycle, the gap closes by 1 each iteration
3. When gap = 0, they meet
4. Fast can never "jump over" slow

Master this proof, and you'll not only solve cycle detection problems—you'll be able to explain why your solution works, which is what separates good engineers from great ones.

For more on two pointers patterns, see the complete guide and fast/slow pointers template.

Next time an interviewer asks "Why does this work?", you'll have a rigorous answer ready.