Cycle Detection: Floyd, Brent & the Proofs

July 2026 · 24 min read

Everyone can recite "tortoise and hare". Far fewer can explain why the two pointers must meet, why the meeting point is where it is, or why restarting one pointer at the head lands exactly on the loop entrance. This post is the one that separates memorising the four lines from understanding them. We will derive every claim with real algebra — and because this series does not load a math renderer, all of it is written in plain notation you can read in any browser.

It builds directly on the previous post: the same different-speed pair that finds the middle also detects a cycle. The only change is the stop condition — instead of stopping when fast falls off the end, we stop when fast catches slow.

The Shape of a List With a Cycle

A linked list that contains a cycle is not a circle — it is the Greek letter rho (ρ): a straight tail that runs into a loop. Two numbers describe it completely:

• μ (mu) — the tail length: the number of next hops from head to the first node that is on the cycle. That first on-cycle node is the entrance. A pure circle has μ = 0.
• λ (lambda) — the cycle length: the number of nodes on the loop, so walking λ hops from any cycle node returns to it.

Position a node by its distance s from the head. For s < μ you are on the tail at node s. For s ≥ μ you are on the cycle at offset (s − μ) mod λ past the entrance. Every statement below is arithmetic on those two facts. The concrete example we will trace throughout has μ = 3 and λ = 4.

The Baseline You Must Beat

Before the clever pointers, know the obvious solution, because in an interview you should state it, give its cost, and then say "but we can do better". Walk the list and record every node address in a hash set; the first address you see twice is proof of a cycle (and is, in fact, a node on the cycle, though not necessarily the entrance).

bool hasCycleHash(ListNode* head) {
    std::unordered_set<ListNode*> seen;
    for (ListNode* p = head; p; p = p->next) {
        if (seen.count(p)) return true;   // revisited => cycle
        seen.insert(p);
    }
    return false;                         // reached nullptr => no cycle
}

This is O(n) time and, decisively, O(n) extra space. Floyd's algorithm matches the time and cuts the space to O(1). That space win is the entire point.

Floyd's Tortoise and Hare

Run slow one hop per step and fast two. If the list ends, fast reaches null first and we report no cycle. If there is a cycle, both pointers eventually enter it and then fast gains ground on slow until it lands on the very same node.

bool hasCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;    // hare lapped the tortoise
    }
    return false;                         // fast hit the end: acyclic
}

Why it terminates without a cycle. Each iteration advances fast by two real nodes. On an acyclic list of length n, fast or fast->next becomes null within ⌈n/2⌉ iterations, so the loop exits. No infinite loop is possible.

Why they must meet with a cycle. Once both pointers are inside the loop, measure the forward distance g from fast to slow around the cycle (how many hops fast is behind slow), with 0 ≤ g < λ. Every step, slow moves +1 and fast moves +2, so fast closes the gap by exactly 1 each step: g becomes g − 1. A quantity in {0, 1, …, λ−1} that drops by one every step reaches 0 within at most λ steps — and g = 0 means the two pointers are on the same node. The chase cannot overshoot, because the gap is measured modulo λ and shrinks by exactly one; there is no way to jump past zero.

The Entrance Trick, Proved

Detecting a cycle is easy; the beautiful part is finding where the loop begins. The algorithm is almost suspiciously short: at the meeting point, reset one pointer to head, then advance both one hop at a time; they meet at the entrance.

ListNode* detectCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {                // phase 1: find a meeting point
            ListNode* p = head;
            while (p != slow) {            // phase 2: march to the entrance
                p = p->next;
                slow = slow->next;
            }
            return p;                      // the cycle entrance
        }
    }
    return nullptr;
}

Here is the full derivation. Let μ be the tail length and λ the cycle length. Suppose the pointers meet after slow has taken d steps; then fast has taken 2d steps, because it moves twice as fast.

Notice you never need to know μ or λ to run the algorithm — the algebra guarantees the two pointers synchronise at the entrance regardless of their values. The proof also quietly explains why fast must be reset (or a fresh pointer used) rather than slow: it is the head-anchored pointer travelling μ that pins the entrance.

A Concrete Run: μ = 3, λ = 4

Label the tail t0 → t1 → t2 and the cycle c0 → c1 → c2 → c3 → c0, so c0 is the entrance (μ = 3) and the loop has λ = 4 nodes. The animation walks both phases; the table under it is the same run in numbers.

Using node(s) = s for s < 3 and node(s) = c[(s−3) mod 4] otherwise, the same run reads:

s      :  0    1    2    3    4
slow   : t0   t1   t2   c0   c1
fast   : t0   t2   c1   c3   c1
                              ^ meet at c1 (s = 4)

They meet at c1 after d = 4 tortoise-steps. Check the proof: d = 4 and d mod λ = 4 mod 4 = 0 — a whole number of laps, as claimed. The meeting node c1 sits at offset (d − μ) mod λ = (4 − 3) mod 4 = 1 past the entrance, and indeed c1 is one node after c0. Now phase 2:

step   :  0    1    2    3
p (head): t0   t1   t2   c0
q (meet): c1   c2   c3   c0
                         ^ meet at c0 = the entrance, after mu = 3 steps

Both land on c0 after three steps — exactly μ — and c0 is the entrance. The algebra and the trace agree.

Cycle Length, Tail Length, and Removal

Once you hold a node known to be on the cycle (the meeting point), the cycle length λ is one more walk: step forward counting until you return to where you started.

int cycleLength(ListNode* meeting) {
    int len = 1;
    for (ListNode* p = meeting->next; p != meeting; p = p->next) ++len;
    return len;
}

The tail length μ falls out of phase 2 for free — it is simply the number of steps the head pointer took to reach the entrance. And once you have the entrance, breaking the cycle is a single pointer write: walk from the entrance λ−1 hops to the last cycle node (the one whose next is the entrance) and set that next to null.

Brent's Algorithm: Fewer Dereferences

Floyd advances three next pointers per iteration (one for slow, two for fast). Brent's algorithm finds the same cycle while evaluating next only once per iteration, by keeping the tortoise still and letting the hare run in phases whose length doubles: 1, 2, 4, 8, … The tortoise teleports to the hare at the start of each new phase; a collision within a phase reveals the cycle.

// Detect a cycle and, if present, report its length lambda.
bool brentCycle(ListNode* head, long& lambda) {
    if (!head) return false;
    long power = 1;
    lambda = 1;
    ListNode* tortoise = head;
    ListNode* hare = head->next;
    while (tortoise != hare) {
        if (!hare) return false;          // ran off the end: acyclic
        if (power == lambda) {            // begin a new, longer phase
            tortoise = hare;
            power *= 2;
            lambda = 0;
        }
        hare = hare->next;
        ++lambda;
    }
    return true;                          // tortoise == hare: cycle length is lambda
}

Brent's makes at most a constant factor fewer node visits than Floyd — and crucially it recovers λ as a by-product, whereas Floyd needs an extra walk. The distinction matters most when following next is expensive. In Pollard's rho factorisation the "successor" is a modular multiply, and in general functional-graph search it may be any costly function; there, halving the number of evaluations is a real speedup, not a micro-optimisation. On a plain in-memory linked list, where next is one load, Floyd's simpler code usually wins in practice.

Any Iterated Function Has a Rho

The deep reason these tricks generalise: a linked list is just the sequence x, f(x), f(f(x)), … where f is "follow next". Any function f from a finite set to itself produces the same rho shape when iterated — a tail that runs into a cycle — because the sequence must eventually repeat a value, and from the first repeat onward it loops. So Floyd and Brent detect cycles in any iterated map, not only in pointer-linked nodes.

Happy Number (LeetCode 202). Define f(x) = sum of the squares of the digits of x. Iterating either reaches 1 (happy) or falls into a cycle that never contains 1 (unhappy). That is exactly cycle detection with f as the successor:

int squareDigits(int x) {
    int s = 0;
    while (x) { int d = x % 10; s += d * d; x /= 10; }
    return s;
}
bool isHappy(int n) {
    int slow = n, fast = squareDigits(n);
    while (fast != 1 && slow != fast) {
        slow = squareDigits(slow);
        fast = squareDigits(squareDigits(fast));
    }
    return fast == 1;
}

Find the Duplicate Number (LeetCode 287). Given n + 1 integers each in [1, n], exactly one value repeats; find it without modifying the array or using extra space. The trick is to read the array as a function: define f(i) = nums[i]. Indices live in [0, n] and values in [1, n], so f maps an index to another valid index — it is a functional graph. A duplicate value v means two different indices both map to v, so node v has two arrows pointing at it: it is the entrance of a cycle. Floyd finds it.

int findDuplicate(std::vector<int>& nums) {
    int slow = nums[0];
    int fast = nums[0];
    do {                                  // phase 1: meet inside the cycle
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);
    slow = nums[0];                       // phase 2: find the entrance
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;                          // the duplicated value
}

The index-to-value mapping is the whole insight: starting from index 0 and repeatedly jumping to nums[current] traces a path through a functional graph whose only possible cycle entrance is the repeated value. The exact same two-phase Floyd routine that finds a linked-list loop entrance finds the duplicate — O(n) time, O(1) space, array untouched.

Check Yourself

Each situation targets one claim from the proofs above. Pick the statement that is actually true.

Practice

• LeetCode 141 — Linked List Cycle detect Floyd phase 1; stop on collision, return false on null.
• LeetCode 142 — Linked List Cycle II entrance phase 2: reset one pointer to head and march both by one.
• LeetCode 202 — Happy Number functional graph successor is the sum of squared digits; detect the non-1 cycle.
• LeetCode 287 — Find the Duplicate Number array as f treat nums[i] as an edge; the duplicate is the cycle entrance.
• LeetCode 457 — Circular Array Loop generalised same idea with directional, variable-length jumps and a validity check.