Fast & Slow Pointers — Floyd's Cycle Detection

Before we start

You have seen two pointers move in the same direction (Chapter 1.2) and in opposite directions (Chapter 1.1). This chapter introduces a third configuration: two pointers on the same structure, moving at different speeds — one step at a time (slow) and two steps at a time (fast). By the end you will be able to:

• Detect whether a linked list has a cycle in O(n) time, O(1) space.
• Find the exact node where the cycle begins — with a two-phase proof.
• Apply the same idea to the Happy Number problem (cycle detection on a number sequence).

Picture this first (no code yet)

First, the slow way (so you feel the pain)

The obvious approach: keep a visited set. As you traverse, check if the current node is already in the set.

def hasCycle_set(head):
    seen = set()
    node = head
    while node:
        if id(node) in seen:
            return True     # revisited a node — cycle!
        seen.add(id(node))
        node = node.next
    return False

This works, but uses O(n) space — one entry per node. For a list of 10 million nodes, that is 10 million entries in memory. Floyd's algorithm detects the cycle using O(1) space — just two pointer variables, regardless of list length.

For n = 10 000 000: visited-set uses ~400 MB of memory. Floyd uses 8 bytes (two pointers). Same time complexity — O(n) — radically different space.

The turning point

The one idea to remember

Part 1 — Cycle detection

def hasCycle(head):
    slow = fast = head
    while fast and fast.next:         # fast needs two steps — check both
        slow = slow.next              # one step
        fast = fast.next.next         # two steps
        if slow is fast:
            return True               # met inside cycle
    return False                      # fast hit None — no cycle

Frame-by-frame: 1 → 2 → 3 → 4 → 2 (cycle at node 2)

Initial: slow=1, fast=1

Step 1: slow=2, fast=3
Step 2: slow=3, fast=2   (fast looped: 3→4→2)
Step 3: slow=4, fast=4   (slow: 3→4, fast: 2→3→4... wait let me re-trace)

List: 1 → 2 → 3 → 4 → (back to 2)

Step 1: slow = node2, fast = node3
Step 2: slow = node3, fast = node2  (fast: node3→node4→node2)
Step 3: slow = node4, fast = node4  (fast: node2→node3→node4)

slow is fast at node4 → cycle detected ✅

Frame-by-frame: 1 → 2 → 3 (no cycle)

slow=1, fast=1
Step 1: slow=2, fast=3
Step 2: fast=fast.next.next = node3.next.next = None.next → fast.next is None → while condition fails
Return False ✅

Part 2 — Find the cycle entry point (LC #142)

This is the harder variant: not just "does a cycle exist?" but "at which node does the cycle begin?"

The answer comes from a beautiful mathematical property of where slow and fast meet.

The math (plain words, no symbols)

Let:

• F = distance from head to the cycle entry point
• C = length of the cycle
• a = distance from cycle entry to the meeting point (measured forward around the cycle)

When they meet:

• Slow has traveled: F + a steps
• Fast has traveled: F + a + C steps (it has gone around the cycle one full extra time)
• Fast travels twice as far: F + a + C = 2(F + a)

Solving: C - a = F

This says: the distance from the meeting point back to the cycle entry (going forward around the cycle) equals the distance from the head to the cycle entry.

So: reset one pointer to the head, keep the other at the meeting point, and move both one step at a time. They will meet exactly at the cycle entry.

def detectCycle(head):
    slow = fast = head

    # Phase 1: find meeting point
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            break
    else:
        return None          # no cycle

    # Phase 2: find cycle entry
    slow = head              # reset one pointer to head
    while slow is not fast:  # keep other at meeting point
        slow = slow.next
        fast = fast.next     # both move ONE step now

    return slow              # they meet at the cycle entry

Frame-by-frame: 3 → 1 → 0 → -4 → (back to 1)

List: 3 → 1 → 0 → -4 → (cycle to 1)
F = 1 (head to node 1)
C = 3 (cycle: 1 → 0 → -4 → 1)

Phase 1 (2-speed):
slow=3, fast=3
Step 1: slow=1,  fast=0
Step 2: slow=0,  fast=1   (fast: 0→-4→1)
Step 3: slow=-4, fast=-4  (fast: 1→0→-4)
Meeting point: node -4

Phase 2 (1-speed, slow resets to head=3):
slow=3, fast=-4
Step 1: slow=1, fast=1    ← both at node 1
Return node 1 ✅  (the cycle entry)

Verify: F=1, meeting distance from entry a=2 (entry→0→-4), C-a=3-2=1=F ✅

Application: Happy Number (LC #202)

A "happy number" is defined by repeatedly replacing n with the sum of the squares of its digits. If this process eventually reaches 1, the number is happy. If it cycles endlessly without reaching 1, it is not.

This is cycle detection on a number sequence, not a linked list. Same algorithm:

def isHappy(n: int) -> bool:
    def next_val(x):
        total = 0
        while x:
            x, digit = divmod(x, 10)
            total += digit ** 2
        return total

    slow = n
    fast = next_val(n)

    while fast != 1 and slow != fast:
        slow = next_val(slow)
        fast = next_val(next_val(fast))

    return fast == 1    # if they met at 1, it's happy; if they met elsewhere, it's a cycle

The key insight: unhappy numbers always end up in the cycle 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4. The fast/slow pointers detect this cycle in O(log n) steps per next_val call.

Where to spot this pattern

Trigger words:

• "detect cycle in linked list"
• "find where the cycle begins"
• "happy number" / "any repeated state in a sequence"
• "find duplicate number" (Duplicate Number with space constraint — Floyd on array indices)
• "find the missing/duplicate" — when you can model it as a function f(i) = array[i]

5 disguises:

1. Linked List Cycle (LC #141): direct application — hasCycle.
2. Linked List Cycle II (LC #142): two-phase — find entry point.
3. Happy Number (LC #202): Floyd on digit-sum sequence.
4. Find the Duplicate Number (LC #287): treat array as linked list f(i) = nums[i]. Duplicate ↔ cycle entry. O(n) time, O(1) space — no sorting, no set.
5. Palindrome Linked List (LC #234): uses fast/slow to find middle first (Chapter 4.2), then reverses second half.

Common traps

Complexity

Floyd always wins on space. Time is equivalent.

Say it like a pro (interview one-liner)

"I'll use Floyd's fast-and-slow pointer algorithm — slow moves one step, fast moves two. If they meet, a cycle exists. To find the cycle entry, I reset slow to the head and move both one step at a time — they meet at the entry because the head-to-entry distance equals the meeting-point-to-entry distance around the cycle. O(n) time, O(1) space."

# Phase 1: detect & find meeting point
slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow is fast: break   # cycle found
else: return None            # no cycle

# Phase 2: find cycle entry
slow = head                  # reset one pointer
while slow is not fast:
    slow = slow.next
    fast = fast.next         # both ONE step now
return slow                  # cycle entry node

Check yourself

Practice problems

Next up: Find Middle of Linked List — the simplest fast/slow application: when fast reaches the end, slow is exactly at the middle.