Fast and Slow Pointers: Floyd's Cycle Detection

Terminology

Term	Definition
Fast pointer	A pointer that advances two steps per iteration. It traverses the structure at double speed relative to the slow pointer.
Slow pointer	A pointer that advances one step per iteration. When a cycle exists, the fast pointer will eventually catch up to it.
Cycle	A loop in a linked list where a node's next pointer points back to a previously visited node, causing infinite traversal.

Floyd's algorithm A two-phase algorithm: phase 1 detects a cycle using fast/slow pointers, phase 2 finds the exact entry point of the cycle. Cycle length The number of nodes in the cycle. Denoted $C$. Once the fast and slow pointers meet inside the cycle, walking one pointer $C$ more steps returns it to the meeting point. Tail length The number of nodes before the cycle entry point. Denoted $\lambda$. Floyd's phase 2 exploits the relationship between $\lambda$ and the meeting point. Happy number A number where repeatedly summing the squares of its digits eventually reaches 1. If it never reaches 1, the sequence enters a cycle. Functional graph A directed graph where every node has exactly one outgoing edge. Linked lists and digit-sum sequences are functional graphs, and they always contain a "rho" ($\rho$) shape: a tail leading into a cycle.

What & Why

Given a linked list, how do you detect whether it contains a cycle, and if so, where the cycle begins? You could use a hash set to track visited nodes, but that costs $O(n)$ space. Floyd's cycle detection algorithm solves both problems in $O(n)$ time and $O(1)$ space using just two pointers.

The slow pointer moves one node at a time. The fast pointer moves two nodes at a time. If there is no cycle, the fast pointer reaches the end. If there is a cycle, the fast pointer eventually laps the slow pointer and they meet inside the cycle.

This technique extends beyond linked lists. Any sequence defined by a function $f(x)$ (where the next value depends only on the current value) forms a functional graph with a rho shape. The happy number problem, duplicate detection in arrays, and pseudorandom number generator cycle analysis all use this same idea.

How It Works

Phase 1: Detecting the Cycle

Both pointers start at the head. The slow pointer moves one step, the fast pointer moves two steps. If they meet, a cycle exists.

Phase 2: Finding the Cycle Start

After the pointers meet, reset one pointer to the head. Now advance both pointers one step at a time. They will meet at the cycle entry node.

Why does this work? Let $\lambda$ be the tail length and $C$ the cycle length. When they first meet, the slow pointer has traveled $\lambda + k$ steps inside the cycle. The fast pointer has traveled $2(\lambda + k)$ steps. The difference $\lambda + k$ must be a multiple of $C$. So starting one pointer at the head and one at the meeting point, both moving one step at a time, they converge at the cycle entry after exactly $\lambda$ steps.

Complexity Analysis

Operation	Time	Space
Cycle detection (phase 1)	$O(n)$	$O(1)$
Find cycle start (phase 2)	$O(n)$	$O(1)$
Hash set approach	$O(n)$	$O(n)$
Happy number check	$O(\log n)$ per step, $O(1)$ cycle length	$O(1)$

Phase 1 terminates in at most $\lambda + C$ steps for the slow pointer, where $\lambda$ is the tail length and $C$ is the cycle length. Since $\lambda + C \leq n$, the total is $O(n)$. Phase 2 takes exactly $\lambda$ additional steps.

Implementation

Linked List Cycle Detection

ALGORITHM HasCycle(head)
  INPUT: head node of a linked list
  OUTPUT: TRUE if cycle exists, FALSE otherwise

  slow = head
  fast = head

  WHILE fast != NULL AND fast.next != NULL DO
    slow = slow.next
    fast = fast.next.next

    IF slow = fast THEN
      RETURN TRUE
    END IF
  END WHILE

  RETURN FALSE
END

Find Cycle Start Node

ALGORITHM FindCycleStart(head)
  INPUT: head node of a linked list (known to have a cycle)
  OUTPUT: the node where the cycle begins

  slow = head
  fast = head

  // Phase 1: detect meeting point
  REPEAT
    slow = slow.next
    fast = fast.next.next
  UNTIL slow = fast

  // Phase 2: find entry point
  finder = head
  WHILE finder != slow DO
    finder = finder.next
    slow = slow.next
  END WHILE

  RETURN finder
END

Happy Number

ALGORITHM IsHappy(n)
  INPUT: positive integer n
  OUTPUT: TRUE if n is a happy number, FALSE otherwise

  FUNCTION DigitSquareSum(x)
    total = 0
    WHILE x > 0 DO
      digit = x MOD 10
      total = total + digit * digit
      x = x / 10   // integer division
    END WHILE
    RETURN total
  END FUNCTION

  slow = n
  fast = n

  REPEAT
    slow = DigitSquareSum(slow)
    fast = DigitSquareSum(DigitSquareSum(fast))
  UNTIL slow = fast

  RETURN slow = 1
END

Real-World Applications

• Garbage collection: cycle detection in reference graphs helps identify unreachable object clusters in memory management systems.
• Deadlock detection: operating systems model resource dependencies as directed graphs. A cycle in the wait-for graph indicates a deadlock.
• Pseudorandom number generators: Floyd's algorithm determines the cycle length and tail length of PRNG sequences, which is critical for assessing randomness quality.
• Linked list middleware: detecting corrupted pointers in data structures that form unintended cycles, preventing infinite loops in production systems.
• Cryptographic hash collisions: Pollard's rho algorithm for integer factorization uses Floyd's cycle detection on a pseudorandom sequence modulo $n$.

Key Takeaways

• Fast/slow pointers detect cycles in $O(n)$ time and $O(1)$ space, beating the hash set approach on memory
• Phase 1 (detection) works because the fast pointer closes the gap by one node per iteration inside the cycle
• Phase 2 (finding the entry) exploits the mathematical relationship between tail length, cycle length, and meeting point
• The technique applies to any functional graph (one outgoing edge per node), not just linked lists
• The happy number problem is a disguised cycle detection problem: the digit-square-sum sequence either reaches 1 or enters a cycle