Detect a Loop in a Linked List — Floyd's Cycle Detection with Cycle Start

Floyd's algorithm (tortoise and hare)

• slow = head, fast = head
• slow advances 1 step, fast advances 2
• If they meet: cycle detected
• If fast or fast.next is null: no cycle

Time O(n), Space O(1)

Why it works

• No cycle: fast reaches end first
• Cycle: both eventually inside; fast gains 1 step on slow per iteration
• Within C iterations (C = cycle length), gap becomes 0

Critical null check

• fast != null && fast.next != null
• Needed because we dereference fast.next.next
• Without: NPE

Finding cycle length

• After meeting, fix one pointer, advance the other
• Count steps until back at same position
• That count = cycle length

Finding cycle start (phase 2)

• After detecting cycle: reset one pointer to head
• Advance both at speed 1
• They meet at cycle start

The math

• L = distance head → cycle start
• C = cycle length
• D = distance cycle start → meeting point
• Slow traveled L+D; fast traveled L+D+kC
• Fast = 2 × slow: 2(L+D) = L+D+kC
• Simplify: L = kC - D
• Meaning: distance from head to start = distance from meeting to start (mod C)
• Walking both at speed 1 converges at the start

Edge cases

• Empty: head null → false/null
• Single node, no cycle: fast.next null, false
• Single node, self-loop: both at same node → true
• Cycle at head: L = 0, phase 2 returns head immediately
• Cycle of length 1: detected correctly

Alternatives

HashSet

• Track visited nodes by reference
• O(n) time, O(n) space
• First re-seen node = cycle start (trivial)
• Simpler to code
• Use when memory not critical

Brent's algorithm

• Teleport slow to fast at exponential intervals
• ~36% fewer pointer advances
• Less well-known
• Competitive programming

Mutation (visited flag)

• Add a boolean to each node
• O(n) time, O(1) extra space (per-node flag overhead)
• Usually forbidden (shared lists, immutable data)
• Don't use unless explicitly allowed

Common bugs

1. NPE on fast.next.next

• Must check both fast and fast.next before advancing

2. Confusing meeting point with cycle start

• They're different!
• Need phase 2 to find start

3. Not understanding the math

• Interviewers often ask to prove
• Memorize L = kC - D

4. Wrong restart in phase 2

• Start one pointer at head
• Keep the other at meeting point
• Not: both at meeting point

5. Wall-time assumption

• Pointer chasing is cache-unfriendly
• HashSet allocation may offset O(n) space cost
• Benchmark in production

Generalization — beyond linked lists

Happy number

• next(n) = sum of squares of digits
• Reaches 1 (happy) or cycles
• Apply Floyd's to integer sequence
• O(log n) per step, bounded iterations

Find duplicate in [1..n] array of size n+1

• Treat array as function f(i) = nums[i]
• By pigeonhole, cycle exists
• Cycle start = duplicate
• O(n) time, O(1) space
• Beats sorting (O(n log n)) and hashing (O(n) space)

PRNG cycles

• Pseudo-random number generators have finite state
• Cycles matter for cryptography
• Floyd's / Brent's detect them

Key insight

• Any deterministic 'next' function on a bounded state space — Floyd's applies
• O(1) space is the headline advantage

For interviews

• Floyd's is the expected answer
• HashSet is acceptable with trade-off explanation
• Don't reach for mutation unless allowed

Recommendation: For cycle detection in linked lists, Floyd's algorithm is the canonical interview answer — O(n) time, O(1) space. Memorize the two-phase pattern: (1) slow/fast meet → cycle detected; (2) reset one pointer to head, advance both at speed 1, they meet at cycle start. Be ready to prove the math (L = kC - D) because interviewers often ask 'why does phase 2 work?' Know how to find cycle length too: from the meeting point, walk the cycle once. Always check `fast != null && fast.next != null` before advancing to avoid NPE on fast.next.next. For edge cases, handle empty list, single node, self-loop, and cycles at the head. For alternatives, HashSet is acceptable (O(n) space, simpler, first-re-seen = cycle start) but Floyd's is preferred when memory matters. Don't reach for node mutation (adding a visited flag) unless explicitly allowed — shared or immutable data structures forbid it. The pattern generalizes beyond linked lists: any deterministic state transition with bounded state (happy number, find duplicate in [1..n], PRNG cycles) admits Floyd's with O(1) space. The mental model: any sequence with a deterministic next can be cycle-detected with fast/slow, using space proportional to nothing but the two pointers themselves. Know the algorithm cold; the math proof is the differentiator.