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.
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).
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.
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
}
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.
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:
.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.