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