Tortoise and Hare (Floyd's Cycle Detection)

How tortoise-and-hare works

Treat the sequence as a function chase: each node x has a unique successor f(x). Start two pointers at the head. Move tortoise by 1 step (tortoise = f(tortoise)) and hare by 2 steps (hare = f(f(hare))) per iteration. If hare ever falls off a non-cyclic chain, no cycle exists. If hare equals tortoise, a cycle exists and they collided inside it.

• Phase 1 — detection: step until hare collides with tortoise or hare reaches null.
• Phase 2 — find entry: reset tortoise to the start; step tortoise and hare both by 1; they meet at the cycle entry.
• Phase 3 (optional) — measure cycle length: freeze tortoise, step hare alone, count steps until they re-collide.

The whole procedure visits each node O(1) times and uses two pointers — no auxiliary memory.

The two-phase math

Let μ = distance from start to the cycle entry, and λ = cycle length. After μ tortoise steps, tortoise enters the cycle; the hare has moved 2μ, so it is at offset μ mod λ inside the cycle. The relative speed of hare over tortoise is 1 step per iteration — they collide after λ − (μ mod λ) more iterations.

The collision point is at offset (μ + (λ − μ mod λ)) = (some multiple of λ) − μ mod λ inside the cycle, equivalently at distance μ mod λ before the entry going forward, or μ from the start going through the entry.

That equality is the trick: the distance from the start to the entry equals the distance from the collision point to the entry, modulo λ. Restart tortoise at the start, walk tortoise and hare both by 1 step. After exactly μ steps, both stand at the entry.

JavaScript implementation

// Detect cycle in a linked list, return entry node or null
function detectCycle(head) {
  if (!head) return null;
  let tortoise = head, hare = head;
  // Phase 1: detect collision
  while (hare && hare.next) {
    tortoise = tortoise.next;
    hare = hare.next.next;
    if (tortoise === hare) break;
  }
  if (!hare || !hare.next) return null;  // no cycle
  // Phase 2: find entry
  tortoise = head;
  while (tortoise !== hare) {
    tortoise = tortoise.next;
    hare = hare.next;
  }
  return tortoise;  // == hare, the cycle entry
}

// Cycle length
function cycleLength(meet) {
  let count = 1, p = meet.next;
  while (p !== meet) { p = p.next; count++; }
  return count;
}

Python implementation

def detect_cycle(head):
    if not head:
        return None
    tortoise = hare = head
    # Phase 1
    while hare and hare.next:
        tortoise = tortoise.next
        hare = hare.next.next
        if tortoise is hare:
            break
    else:
        return None  # hare reached end → no cycle
    # Phase 2
    tortoise = head
    while tortoise is not hare:
        tortoise = tortoise.next
        hare = hare.next
    return tortoise

def cycle_length(meet):
    count, p = 1, meet.next
    while p is not meet:
        p = p.next
        count += 1
    return count

Iterated functions — beyond linked lists

Any function f: S → S on a finite set S eventually cycles when iterated. Tortoise-and-hare detects the cycle without ever materializing the full sequence. Replace .next with f(x):

function findDuplicateInRange(nums) {
  // nums has n+1 entries in [1..n]; one duplicate. Treat nums as f.
  let tortoise = nums[0], hare = nums[0];
  do {
    tortoise = nums[tortoise];
    hare = nums[nums[hare]];
  } while (tortoise !== hare);
  tortoise = nums[0];
  while (tortoise !== hare) {
    tortoise = nums[tortoise];
    hare = nums[hare];
  }
  return tortoise;
}

This solves "find the duplicate number" in O(n) time and O(1) space — a famous interview application of Floyd's algorithm to an array, not a linked list.

Brent's improvement

Richard Brent (1980) introduced a variant that calls f only once per step, instead of three times (two by hare, one by tortoise). The idea: keep tortoise stationary while hare leaps a power-of-2 distance. If hare passes tortoise, you've detected a cycle; otherwise, double the leap distance and place tortoise at hare's new spot.

function brent(start, f) {
  let power = 1, lam = 1;
  let tortoise = start, hare = f(start);
  while (tortoise !== hare) {
    if (power === lam) {
      tortoise = hare;
      power *= 2;
      lam = 0;
    }
    hare = f(hare);
    lam++;
  }
  // Find μ
  tortoise = hare = start;
  for (let i = 0; i < lam; i++) hare = f(hare);
  let mu = 0;
  while (tortoise !== hare) {
    tortoise = f(tortoise);
    hare = f(hare);
    mu++;
  }
  return { mu, lam };
}

On average Brent calls f about 36% fewer times than Floyd. Pollard's rho factorization with Brent's variant is the default in number-theory libraries (GMP, PARI/GP).

Pollard's rho factorization

To factor a composite number n, define a pseudorandom map f(x) = (x² + c) mod n with random c. Iterate from a random seed; modulo any prime divisor p of n, the orbit cycles in roughly √p iterations (birthday paradox). Apply Floyd's: when |tortoise − hare| shares a non-trivial gcd with n, you've found a factor.

function pollardRho(n) {
  if (n % 2n === 0n) return 2n;
  let x = 2n, y = 2n, c = 1n, d = 1n;
  const f = z => (z * z + c) % n;
  while (d === 1n) {
    x = f(x);
    y = f(f(y));
    d = gcd(x > y ? x - y : y - x, n);
  }
  return d === n ? null : d;  // retry with new c if d == n
}

Pollard's rho factored an 8-decimal-digit number in 1975 in seconds — orders of magnitude faster than trial division for n ≈ 10⁸.

Why tortoise-and-hare matters

• Interview classic. "Detect cycle in linked list" appears in roughly 30% of FAANG screening sets. The follow-up — "find the entry node, in O(1) memory" — is the standard separator question.
• Cryptographic factorization. Pollard's rho with Brent's variant factored RSA-129 (1994) using machine-weeks of compute — a milestone in showing 425-bit moduli were vulnerable.
• Iterated function analysis. Pseudorandom number generators are pure functions f(state) → state; their cycle length determines period quality. Floyd's algorithm tests period length in O(period) time without storing the full sequence.
• Garbage collection bug detection. Reference cycles in mark-and-sweep GCs are detected by tortoise-and-hare on the heap-pointer graph; reference-counting GCs do not detect cycles natively, so they couple with periodic Floyd-style traversal.
• Memory-bounded environments. Embedded systems, kernel-mode code, or hot inner loops where allocating an O(n) hash set is unacceptable use Floyd's because it adds zero memory pressure.
• Sequence equality testing. If two iterated functions produce the same orbit, comparing them is a cycle-equivalence problem — Floyd-style detection is one tool.

Common misconceptions

• "Doubles memory." Two pointers is O(1), not O(2). The whole point of Floyd's is constant extra space — versus the hash-set approach which is O(n).
• "Fails on long chains." Works on any pointer chase. The cycle detection loop terminates either by hare reaching null (no cycle) or by collision (cycle); chain length affects time, not correctness.
• "Hare always wins the race." Hare and tortoise meet inside the cycle; "winning" is a misnomer — it's a chase, not a race, and meeting is success.
• "Can detect cycles in a tree or DAG." Floyd's needs a deterministic successor — a pointer chase. Trees have no cycles by definition; DAGs have multiple successors per node, so plain Floyd's doesn't apply (use Tarjan's SCC instead).
• "Step ratio must be 1:2." Any pair of relatively prime speeds works for detection. The 1:2 pair is cheapest because hare = hare.next.next is a single statement; entry-finding math relies on the 1:2 ratio specifically.
• "Replaces all hash-set cycle detection." If f is non-deterministic or you need to know the step at which a node was first seen, hashing is the right tool. Floyd's is for pure deterministic successor functions.
• "Always faster than hashing." Floyd's makes more f-calls (2 hare + 1 tortoise per iteration). If f is expensive to compute and memory is cheap, hashing's single f-call per step plus O(1) hash insert can be faster wall-clock — verify by benchmark.