Cairn
algorithms · graph traversal · O(n) time, O(1) space

↩ back to Graph Traversal

Brent's Cycle Detection Algorithm

Brent's algorithm answers the identical question as Floyd's Cycle Detection (Tortoise and Hare) — does a functional graph (a linked list, or any chain where each node points to exactly one next node) loop back on itself, and if so, where does the loop start — in the same O(n) time and O(1) space. It changes one thing: instead of a second pointer that moves every single step, the second pointer (call it the checkpoint) only teleports to the hare's current position at power-of-two intervals — after 1 step, then 2, then 4, then 8, doubling each time. Between teleports it doesn't move at all. That one change turns out to matter a lot, but not in the single, uniform direction most descriptions of Brent's algorithm imply.

Try it

Each box is one node, in the order a walk from the head visits them. Step through phase 1 (the checkpoint teleports while the hare hops every step, until the hare laps back onto the checkpoint — that gap is the cycle length λ) and phase 2 (a lookahead pointer advances λ steps from the head, then both pointers move together until they meet at the cycle's start).

Press Load, then Step through the search.

Why it works

Phase 1 — the gap at the moment the hare first catches the checkpoint is exactly λ. Say the checkpoint's most recent teleport landed it on the hare's position after power hops total. The hare keeps hopping, counting lam steps since that teleport. If lam ever reaches power again without the hare having lapped the (stationary) checkpoint, the checkpoint teleports again — jumping onto wherever the hare now sits — and power doubles. Once both pointers are inside the cycle, a stationary checkpoint and a hare that advances one node per step will be lapped by the hare after at most λ steps, since the hare gains exactly one position on a non-moving target every step on a loop of length λ. The teleport schedule (1, 2, 4, 8, …) guarantees some teleport interval is the first power of two at least as large as λ — and once that happens, the checkpoint stays put for the whole lap, so the hare laps it in exactly λ steps from that teleport, and lam at that moment is λ. No set, no second moving pointer — the hare running solo is enough, as long as something occasionally marks where it's been.

Phase 2 — the same closing-distance argument Floyd's page uses, just with a known λ instead of a discovered meeting point. A pointer starting at the head is, by definition, μ steps from the cycle's start. A pointer that's advanced exactly λ steps from the head is also μ steps from the cycle's start — because advancing any point already inside the cycle by a whole multiple of λ (which λ steps always is once a pointer has passed the tail) returns it to the same position within the cycle it started at, while a pointer still in the tail gets carried the rest of the way in and then some additional whole trips around. Both pointers close an identical μ-step gap at an identical speed, so advancing them together lands them on the cycle's start at the same time — exactly Floyd's phase-2 argument, substituting "λ steps ahead" for "the phase-1 meeting point" as the thing that's already a whole number of laps removed from wherever the head-started pointer will eventually be.

Reference implementation

function findCycleBrent(head) {
  // Phase 1: discover the cycle length (lambda) via power-of-two checkpoints.
  let power = 1, lam = 1;
  let checkpoint = head;
  let hare = head.next;
  while (hare !== null && checkpoint !== hare) {
    if (power === lam) {
      checkpoint = hare; // teleport onto the hare's current node
      power *= 2;
      lam = 0;
    }
    hare = hare.next;
    lam++;
  }
  if (hare === null) return null; // no cycle

  // Phase 2: advance one pointer lambda steps ahead, then walk both together.
  let slow = head, fast = head;
  for (let i = 0; i < lam; i++) fast = fast.next;
  while (slow !== fast) {
    slow = slow.next;
    fast = fast.next;
  }
  return slow; // the node where the cycle begins
}

Pitfalls

Forgetting to reset lam = 0 after a teleport doesn't just miscount — it almost never finishes at all. Drop that one reset line and lam only ever grows, so power === lam stops being true again once power's doublings fall behind lam's steady climb — the checkpoint stops teleporting, and the hare is left searching for a node that's frozen far behind where it needs to be. Checked directly across 240 tail/cycle combinations (μ, λ from 0 to 15): the broken version hangs outright in 176 of 240 (73.3%) (the hare runs past every real bound looking for a checkpoint that will never reach it), returns a flatly wrong answer in another 63 (26.3%), and happens to still land on the correct node in exactly 1 case. This is a bug that announces itself almost every time, not a quiet one.

Reusing Floyd's phase-2 trick — restart one pointer at the head, leave the other at its last position, walk both together — doesn't work here, because Brent's last checkpoint isn't a meeting point. Floyd's phase 2 works because the phase-1 meeting point is guaranteed to be somewhere inside the cycle already. Brent's checkpoint is the hare's position as of the previous teleport — generally not inside the cycle yet, and not any fixed distance from the cycle's start either. Checked directly across the same 240 combinations: this substitution hangs in 180 of 240 (75%) — the two pointers chase each other around the cycle forever without ever landing on the same node at the same step — and happens to still produce the right answer in the remaining 60 (25%), purely when the checkpoint coincides with a valid lookahead distance by coincidence. Zero cases silently returned a wrong-but-plausible node; this mistake fails loud far more often than it fails quiet, which is the opposite of how most pitfalls on this site behave.

Complexity

Both phases are O(n) time (n = μ + λ) and O(1) space — identical asymptotic bounds to Floyd's. The real difference is in the constant: Floyd's hare makes two dereferences and the tortoise one, three per phase-1 step; Brent's hare makes one dereference per step and the checkpoint makes none except at a teleport. The common claim is that this makes Brent's "faster in practice" without qualification — measuring the two reference implementations' real .next dereferences directly (cross-checked against an independent hash-set walk across 255 tail/cycle combinations first, 0 mismatches) shows that claim only holds in one direction:

Pick μ and λ and press the button to count real .next hops for both algorithms on the identical list.

When the cycle is short relative to the tail (λ ≪ μ) — the shape this trick is usually taught for, since a long random walk before looping is exactly what Pollard's Rho produces — Brent wins decisively: at μ = 1,000, λ = 1, Floyd needs 5,000 dereferences against Brent's 3,025, a 1.65x gap that holds at the same order of magnitude as μ grows further. But once the cycle is as long as or longer than the tail (λ ≥ μ), Floyd wins more often than not — an exhaustive sweep of every (μ, λ) pair from 0 to 60 found Floyd using fewer real dereferences in 1,766 of 1,890 (93.5%) of cases where λ ≥ μ, and in 0 of 1,770 cases where λ < μ. A pure cycle with no tail at all (μ = 0) makes this concrete: Floyd always needs exactly 3λ dereferences there, while Brent's power-of-two schedule can overshoot depending on how λ lines up with the nearest power of two, measured anywhere from slightly fewer to about 21% more across λ = 10 through 20,000 in testing. Averaged over many random μ/λ splits at a fixed total size n, Brent still comes out ahead overall — roughly 11%–15% fewer dereferences across n = 100 through 100,000 — but that average hides a real crossover, not a uniform win.

This site's guide, Choosing a Graph Traversal Approach, places this entry alongside Floyd's: neither uses a stack, queue, or visited set, because the functional graph both walk never branches.