Fast and Slow Pointers: Cycle Detection & Invariants

The Fast and Slow Pointers pattern (often called Floyd's Cycle-Finding Algorithm or the Tortoise and Hare algorithm) is an algorithmic pointer technique where two references traverse a data structure or sequence at different velocities—typically 1 step vs 2 steps per tick.

While a naive approach to detecting cycles or finding middle nodes relies on hash sets or multiple traversal passes that waste O(N) memory, the fast-and-slow strategy delivers O(N) time with strict O(1) auxiliary space.

The Mathematical Invariant: Why Do They Always Meet?

Consider a linked list containing a cycle of length C. Once both pointers enter the loop, every iteration reduces the distance between the fast pointer and the slow pointer by exactly 1 node:

flowchart LR
    Head([Head]) --> N1["Node 1"]
    N1 --> Entry["Cycle Entry (Node 2)"]
    Entry --> Loop1["Node 3 (Slow: +1)"]
    Loop1 --> Loop2["Node 4"]
    Loop2 --> Loop3["Node 5 (Fast: +2)"]
    Loop3 --> Entry

Because the gap shrinks by 1 on every step, the fast pointer cannot skip over the slow pointer; it is guaranteed to collide within at most C iterations once the slow pointer enters the cycle.

Phase 1 & Phase 2: Finding the Exact Cycle Entry Point

Detecting that a loop exists is only half the battle. Finding the start of the cycle requires understanding Floyd's mathematical offset:

1. Let F be the distance from the head to the cycle entry point.
2. Let a be the distance from the cycle entry to the collision point.
3. Let C be the total cycle length.

When collision occurs:

• Distance traveled by slow pointer: d(slow) = F + a
• Distance traveled by fast pointer: d(fast) = F + kC + a (where k is integer loops)
• Since fast moves at 2x speed: 2(F + a) = F + kC + a ⇒ F = kC - a

The takeaway: If you reset one pointer back to the head and keep the other at the collision node, moving both at 1 step per iteration guarantees they will collide exactly at the cycle entrance after F steps.

flowchart TD
    A["slow = head, fast = head"] --> B["slow = slow.next\nfast = fast.next.next"]
    B --> C{"slow == fast ?"}
    C -->|No| D{"fast == null || fast.next == null ?"}
    D -->|Yes| E(["No Cycle Detected (Return null)"])
    D -->|No| B
    C -->|Yes: Phase 1 Complete| F["Reset slow = head\nKeep fast at collision"]
    F --> G["slow = slow.next\nfast = fast.next (Step 1-by-1)"]
    G --> H{"slow == fast ?"}
    H -->|No| G
    H -->|Yes| I(["Cycle Entry Point Located!"])

Pattern 1: Finding the Middle of a Linked List

To split a list (such as during Merge Sort) in a single pass without computing its length beforehand:

Java Implementation

public class LinkedListMiddle {
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
    }

    /**
     * Returns the middle node (second middle for even-length lists).
     */
    public static ListNode findMiddle(ListNode head) {
        if (head == null) return null;

        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow; // Points directly to the middle node
    }
}

Pattern 2: Detecting Cycle & Finding Entry Point

Python Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def detect_cycle_entry(head: ListNode | None) -> ListNode | None:
    """Returns the node where the cycle begins, or None if no cycle exists."""
    if not head or not head.next:
        return None

    slow = head
    fast = head

    # Phase 1: Determine if a cycle exists
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None  # Reached end of list without cycle

    # Phase 2: Locate cycle start node
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next

    return slow

Pattern 3: Implicit Graph Cycles (Happy Number Problem)

The Fast and Slow pointer pattern is not restricted to linked lists. It applies to any state-transition graph where each state has a deterministic next state.

For example, in the Happy Number problem, a number is replaced by the sum of the squares of its digits. If the sequence reaches 1, it stays at 1. If it gets trapped in an infinite loop (e.g., 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4), fast and slow pointers detect the loop without needing a hash set.

TypeScript Implementation

function getSumOfSquares(n: number): number {
  let sum = 0;
  while (n > 0) {
    const digit = n % 10;
    sum += digit * digit;
    n = Math.floor(n / 10);
  }
  return sum;
}

export function isHappyNumber(n: number): boolean {
  let slow = n;
  let fast = getSumOfSquares(n);

  while (fast !== 1 && slow !== fast) {
    slow = getSumOfSquares(slow);
    fast = getSumOfSquares(getSumOfSquares(fast));
  }

  return fast === 1;
}

Core Pitfalls & Invariant Checklist

• Null Pointer Guard: Always guard fast != null && fast.next != null in the while loop condition. Evaluating fast.next.next before verifying fast.next triggers runtime exceptions.
• Even vs. Odd Middle: If you need the first middle node of an even-length list (for splitting lists before reversal), stop when fast.next == null || fast.next.next == null.
• Cycle Length: After detecting collision in Phase 1, you can measure cycle length C by keeping fast fixed and counting how many single steps slow takes to return to fast.

Complexity Comparison