Floyd's Cycle Detection

Detect cycles in a sequence using two pointers at different speeds.

How it works

Floyd's cycle detection algorithm — the tortoise and hare — uses two pointers that traverse a sequence at different speeds to detect whether a cycle exists without any extra memory. The slow pointer advances one node per step while the fast pointer advances two; if a cycle is present, they are guaranteed to meet inside it.

Once a meeting point is found, the algorithm enters a second phase to locate the cycle's entry node. By resetting the slow pointer to the head and advancing both pointers one step at a time from their respective positions, they will meet exactly at the cycle start — a elegant consequence of the mathematical relationship between the list length and cycle length.

The algorithm runs in O(n) time and O(1) space, making it far superior to hash-set approaches for memory-constrained environments.

Complexity

Best case

O(n)

Average case

O(n)

Worst case

O(n)

Space

O(1)

Visualizer

Generating steps…

Where it's used in the real world

Garbage collectors (JVM, Go runtime, CPython)

Detecting circular references in the object graph

Before reclaiming memory, GC must identify objects that form reference cycles (e.g., two objects pointing to each other). Floyd's algorithm detects such cycles without allocating a visited set.

Network routing protocols (RIP, OSPF)

Loop detection in routing tables

Misconfigured routers can create forwarding loops where packets circulate forever. The tortoise-and-hare approach is used in route-trace utilities to detect and report such loops efficiently.

PRNG testing and cryptanalysis

Finding the period of a pseudo-random sequence

Many PRNGs produce sequences that eventually cycle. Floyd's algorithm determines the cycle length (period) and offset (rho) in O(λ+μ) time without storing the full sequence history.

Implementation

interface ListNode {
  val: number;
  next: ListNode | null;
}

function detectCycleStart(head: ListNode | null): ListNode | null {
  if (!head) return null;

  let slow: ListNode | null = head;
  let fast: ListNode | null = head;

  // Phase 1: detect meeting point inside cycle
  while (fast !== null && fast.next !== null) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) {
      // Phase 2: find cycle entry
      slow = head;
      while (slow !== fast) {
        slow = slow!.next;
        fast = fast!.next;
      }
      return slow; // cycle start
    }
  }

  return null; // no cycle
}

Related algorithms

Depth-First SearchLive

Explore as deep as possible before backtracking.

O(V+E)

Union-Find (Disjoint Set)Live

Track which elements belong to the same group with near-O(1) union and find.

O(α(n))