Linked List Cycle Detection

Detect whether a singly linked list contains a cycle (i.e., a node whose next pointer points back to an earlier node) in O(n) time and O(1) space, using Floyd’s Tortoise and Hare algorithm: send two pointers from the head, one moving one step at a time, the other moving two. If a cycle exists, they will eventually meet inside the cycle. If the fast pointer falls off the end, there’s no cycle. A clever follow-up algorithm finds the start of the cycle in another O(n) and O(1).

1. Intuition — Two Runners on a Track

Picture two runners on a closed loop track:

• The slow runner jogs at 1 lap-step per second.
• The fast runner sprints at 2 lap-steps per second.

If the track is a straight line ending at a wall, the fast runner hits the wall and stops — no meeting.

If the track loops back on itself, the fast runner gradually laps the slow one, and at some point they end up at the same place at the same time. They will always meet, because every second the fast runner gains exactly one position on the slow one — and the gap (modulo the cycle length) shrinks by 1 each step.

That’s Floyd’s algorithm. The “track” is the linked list; the “wall” is the null end of an acyclic list; the “meeting” is your cycle-detection signal.

2. The Setup

A singly linked list node:

class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

A linked list with a cycle:

head → A → B → C → D → E
                   ↑     |
                   ←─────┘

Here E.next points back to C. There’s no null terminator anywhere on the cycle. A naive while node: node = node.next loops forever.

3. The Algorithm — Tortoise and Hare

3.1 Pseudocode

has_cycle(head):
    if head == null: return false
    slow := head
    fast := head
    while fast != null and fast.next != null:
        slow := slow.next
        fast := fast.next.next
        if slow == fast:
            return true
    return false

3.2 Python

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

That’s it. Eight lines. The trick is in the proof.

4. Why It Works (Proof Sketch)

Case 1 — No cycle. The fast pointer eventually reaches null (it advances 2 steps per iteration; if there’s a finite end, it gets there in n/2 iterations). Loop exits, return false. ✓

Case 2 — Cycle exists. Both pointers eventually enter the cycle. Once both are on the cycle, the gap between them (measured forward along the cycle) shrinks by exactly 1 each iteration:

• slow moves 1 step forward
• fast moves 2 steps forward
• net: fast catches up by 1

Since the gap is a non-negative integer mod the cycle length C, after at most C iterations the gap is 0 — they meet. ✓

Why specifically 1 and 2? Make the argument precise. Let the slow pointer advance s nodes per iteration and the fast pointer advance f nodes per iteration, with f > s. Once both are on the cycle, write g for the forward gap from slow to fast measured along the cycle, i.e. g = (position(fast) − position(slow)) mod C, where C is the cycle length and mod C reflects that positions wrap. Each iteration the gap changes by f − s (fast gains f − s on slow), so g evolves as g ← (g − (f − s)) mod C if we instead track the deficit slow must make up — equivalently, the displacement d = (f − s) is added to fast’s lead every step. A meeting occurs precisely when the accumulated relative displacement is 0 mod C, i.e. when t · (f − s) ≡ −g₀ (mod C) for some iteration count t, where g₀ is the initial gap upon both entering the cycle. The set of values {t · (f − s) mod C : t = 0, 1, 2, …} is exactly the subgroup of ℤ/Cℤ generated by f − s, which equals {0, gcd(f−s, C), 2·gcd(f−s, C), …}. That subgroup contains the required residue −g₀ for every possible g₀ if and only if it is the whole group — i.e. if and only if gcd(f − s, C) = 1 (GeeksforGeeks, “How Floyd’s slow/fast pointers work”).

Choosing s = 1, f = 2 gives f − s = 1, and gcd(1, C) = 1 for every cycle length C, so a meeting is guaranteed for any cycle — and it happens within at most C iterations because the gap closes by exactly 1 each step. Other pairs can fail: s = 1, f = 3 gives f − s = 2, so on an even-length cycle the reachable gaps are only the even residues; if the pointers enter the cycle with an odd gap they step past each other forever and never coincide. This is why (1, 2) — gap-difference 1 — is the canonical choice rather than an arbitrary convention.

The algorithm carries Floyd’s name, but the credit is murky: it does not appear in Floyd’s own published work. Floyd’s 1967 paper concerns listing all simple cycles in a directed graph, not cycle-finding in a functional graph (a sequence x → f(x)). The first appearance of the attribution in print is Donald Knuth crediting Floyd, without citation, in 1969 (TAOCP Vol. 2). Because no primary publication by Floyd can be found, the cycle-detection community treats it as effectively a folk theorem that may not be attributable to a single individual (per Wikipedia, “Cycle detection”).

5. Tiny Worked Example

List: 1 → 2 → 3 → 4 → 5 → 3 (cycle back to node 3).

Step	slow	fast
0 (init)	1	1
1	2	3
2	3	5
3	4	4 ← meet!

After three iterations, slow and fast meet at node 4. Return true.

6. Finding the Start of the Cycle (Floyd’s Phase 2)

Detection alone is sometimes insufficient — e.g., LeetCode 142, “Linked List Cycle II” asks you to return the node where the cycle begins (or null if there is none), with an explicit follow-up to do it in O(1) memory. Beautiful follow-up:

Algorithm:

1. Run Phase 1 to find the meeting point m.
2. Reset slow to head. Move both slow and a new pointer at m one step at a time.
3. They will meet at the start of the cycle.

def detect_cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            # Phase 2
            slow = head
            while slow is not fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None

Why does Phase 2 work? (The Slick Proof)

Let:

• L = distance from head to the start of the cycle
• C = length of the cycle
• x = distance from the start of the cycle to the meeting point (going around the cycle in the forward direction)

When slow and fast meet, slow has taken some number of steps D; since fast moves twice as fast and started at the same node, fast has taken exactly 2D steps. Both pointers are now at the same node on the cycle, so they sit at the same position around the cycle. Two walkers standing on the same cycle node have travelled distances that differ by a whole number of laps — formally, 2D − D = D must be a multiple of the cycle length C. (This is the step the proof must not skip: equality of positions on a cycle means equality of distances modulo C, hence the difference is a multiple of C.)

Now compute D. Slow entered the cycle after L steps and then walked x more steps around it to reach the meeting point, so D = L + x. Substituting:

2D − D = D = L + x = k · C   for some integer k ≥ 1

(k ≥ 1 rather than k = 0 because fast must have completed at least one full extra lap to catch slow.) Rearranging:

L = k·C − x = (k − 1)·C + (C − x)

Interpretation, term by term: (C − x) is the forward distance from the meeting point onward to the cycle start (the meeting point sits x past the start, so C − x more steps complete the loop back to the start). The leading (k − 1)·C is just (k − 1) extra full laps, which return you to wherever you began. So walking L steps forward from the meeting point lands exactly on the cycle start. This matches the formulation in cp-algorithms, which derives the equivalent identity a = (y − 2x)·λ − b for entry offset a, cycle length λ, and meeting-offset b.

So if we start one pointer at head and another at the meeting point, both moving 1 step per iteration:

• The head pointer reaches the cycle start after L steps.
• The meeting-point pointer is also at the cycle start after L steps (because it’s gone (k-1)·C + (C - x) = L from the meeting point, ending at cycle start).

They meet at the cycle start. ✓

This is one of the most beautiful little proofs in algorithms — the kind interviewers love to ask candidates to derive on the spot.

7. Alternative — Hash Set

The “non-Floyd” answer:

def has_cycle_hashset(head):
    seen = set()
    while head:
        if head in seen:
            return True
        seen.add(head)
        head = head.next
    return False

O(n) time, O(n) space. Conceptually obvious; what Floyd’s wins is the O(1) space.

In an interview, you should:

1. Mention the hash-set approach first as the obvious solution.
2. Then offer Floyd’s as a space-optimization.
3. Be ready to derive the cycle-start algorithm if asked.

8. Brent’s Algorithm — A Faster Alternative

Richard Brent published a different cycle-finding method in 1980 as part of an improved integer-factorization algorithm (Brent, “An improved Monte Carlo factorization algorithm,” BIT 20(2):176–184, 1980). The mechanism is not “teleport the slow pointer at intervals” in the loose sense; the precise rule is worth getting right because interviewers occasionally probe it:

• Keep the tortoise stationary at a saved node. Advance only the hare, one node at a time, comparing it against the saved tortoise position after each step.
• Use a “power” budget that doubles: 2^0 = 1, then 2, 4, 8, …. After the hare has taken power steps without a match, teleport the tortoise to the hare’s current node and double power.
• A match means the hare has lapped exactly onto the saved tortoise node; the number of steps the hare has taken since the last teleport is then the cycle length λ directly — no separate length-finding pass is needed.

Brent’s method has two concrete advantages over the tortoise-and-hare, both noted in the literature (Wikipedia, “Cycle detection”). First, it recovers the cycle length λ as a byproduct rather than requiring a follow-up scan. Second — and this is the source of its speed — each step evaluates the iterated function f only once (advance the hare), whereas Floyd’s must evaluate f three times per iteration (once for slow, twice for fast). When f is expensive — as in Pollard’s rho factorization, Brent’s original setting — that 3:1 ratio dominates. Brent’s own paper claims his cycle-finder runs about 36% faster on average than Floyd’s and speeds up the overall Pollard rho algorithm by about 24% (per Wikipedia, “Cycle detection”, citing Brent 1980). The asymptotic class is identical — both are O(μ + λ) where μ is the tail length and λ the cycle length — so the win is purely in the constant factor and matters most when function evaluation is the bottleneck, not when chasing next pointers in a linked list (where dereference cost is uniform and the 36% rarely shows up). For linked-list interviews, Floyd’s is almost always what is expected; Brent’s is worth naming as “there are tighter variants like Brent’s that find the cycle length directly and evaluate the step function once per iteration.”

9. Beyond Linked Lists — Cycle Detection in Iterated Functions

Floyd’s algorithm is more general than linked lists. It detects cycles in any iterated function x → f(x). Treat each call to f as following a “next” pointer.

Examples

Happy number (LC 202): repeatedly replace n with the sum of squares of its digits. Does the sequence reach 1, or cycle forever?

def is_happy(n):
    def step(x):
        return sum(int(d)**2 for d in str(x))
    slow = fast = n
    while True:
        slow = step(slow)
        fast = step(step(fast))
        if fast == 1: return True
        if slow == fast: return False         # cycle, doesn't include 1

Find the duplicate number (LC 287): in an array of n+1 integers each in [1, n], exactly one duplicate exists. Treat indices as nodes and arr[i] as next(i) — the duplicate causes a cycle, and Phase 2 finds where it starts.

These are classic interview problems that check whether you understand Floyd’s deeply enough to apply outside the linked-list context.

10. Complexity

Operation	Time	Space
has_cycle (Floyd’s)	O(n)	O(1)
has_cycle (hash set)	O(n)	O(n)
detect_cycle_start (Floyd’s Phase 2)	O(n)	O(1)

Why O(n) for Floyd’s? Phase 1 takes at most n iterations of the outer while loop (slow can’t visit more than n distinct positions before being lapped). Phase 2 takes at most L ≤ n iterations. Both are linear.

11. Common Interview Problems

Problem	Pattern
LC 141 — Linked List Cycle	Plain Phase 1
LC 142 — Linked List Cycle II	Phase 1 + Phase 2 (find start)
LC 287 — Find Duplicate Number	Floyd’s on array-as-function
LC 202 — Happy Number	Floyd’s on iterated digit-square sum
LC 234 — Palindrome Linked List	Slow/fast to find middle, then reverse half (related two-pointer use)
LC 876 — Middle of Linked List	Slow/fast (related but no cycle involved)

The slow/fast pointer technique generalizes — finding the middle of a list is a one-liner if you’ve internalized “slow moves at half the speed of fast.”

12. Pitfalls

12.1 null Checks

The condition while fast and fast.next checks both fast and fast.next because we dereference fast.next.next. Forgetting the inner check fast.next causes a null-pointer dereference on acyclic lists.

12.2 Initial Equality

If you initialize slow = fast = head and check if slow == fast before moving them, you’ll always return true (they start equal). Move them first, then compare.

12.3 Off-By-One in Phase 2

Phase 2 starts from head and the meeting point (where Phase 1 found them equal). Mistakes include starting from the wrong place or moving the wrong pointer. Trace through the small example before committing.

12.4 Forgetting Empty / Single-Node Edge Cases

Empty list (head == null) — return false. Single node with next = null — Phase 1’s loop condition fails immediately; false. Single node pointing to itself — Phase 1 enters the loop, slow and fast both move; after one iteration slow == fast (both point to the only node). true.

12.5 Returning the Wrong Thing

Detection vs cycle-start vs cycle-length are different questions. Re-read the prompt; some problems want all three.

12.6 Modifying Pointers

Some “simpler” solutions destroy the list by visiting and rewriting next pointers. Don’t. It violates the typical interview constraint of preserving the input. Floyd’s is non-destructive.

13. Diagram — Floyd’s Two Phases

flowchart LR
  subgraph "Phase 1 — detect"
    H1[head] --> A1[node]
    A1 --> B1[node]
    B1 --> C1[cycle start]
    C1 --> D1[node]
    D1 --> M1["meeting point"]
    M1 --> C1
  end
  subgraph "Phase 2 — find start"
    H2[head/slow] -.move 1 step.-> P1[...]
    M2[fast at meeting] -.move 1 step.-> P2[...]
    P1 --> S[meet at cycle start]
    P2 --> S
  end

What this diagram shows. Phase 1: slow and fast meet somewhere inside the cycle — not necessarily at the start. Phase 2: reset slow to head, move both pointers one step at a time, they meet at the start of the cycle. The math (§6) explains why: distance from head to cycle-start equals distance from meeting-point to cycle-start when both walk forward.

14. Why This Algorithm Matters in Interviews

It’s the canonical “trick” algorithm — the kind that demonstrates algorithmic insight rather than just template knowledge.

• The hash-set solution shows you know the problem.
• Floyd’s shows you can optimize space.
• The cycle-start follow-up shows you can do the math and reason about invariants.
• Generalizing to “find duplicate number” shows you recognize the pattern beyond its surface form.

A candidate who can do all four is signaling senior-level algorithmic depth.

15. Open Questions

• Brent’s “~36% faster” is Brent’s own claim from his 1980 paper, measured for Pollard rho factorization where function evaluation dominates. Its applicability to pointer-chasing on modern cache hierarchies (where Brent’s teleporting tortoise has worse locality than Floyd’s near-adjacent pointers) is not something the paper addresses — needs a dedicated benchmark to claim either way.
• Generalizations to graphs — Floyd’s is for functional graphs (out-degree exactly 1). For general graphs, use DFS with back-edge detection.

16. See Also

• Two Pointers — slow/fast is a special case
• Linked List Reversal — companion linked-list technique
• Singly Linked List
• Depth-First Search — for cycle detection in general graphs
• Big-O Notation
• SWE Interview Preparation MOC