Floyd's Cycle Detection

Tortoise & Hare on a rho-shaped linked list. Build, run, find the cycle start.

Build your list

slow fast

Visualization

tortoise (slow, 1 step)
hare (fast, 2 steps)
cycle entry
meeting point
reset to head
PHASE 1 -- Detection

Step explanation

READY Build a list above (try 1,2,3,4,5 with loop_at=2) then press Play or Step >. Watch the tortoise (blue) advance 1 step and the hare (orange) advance 2 steps. They meet inside the cycle.

Statistics

0
Step
1
Phase
0
Tortoise idx
0
Hare idx
0
(hare - tort) mod λ
?
λ (cycle len)
?
μ (tail len)
no
Cycle?

Big-O

MetricValue
TimeO(μ + λ)
SpaceO(1)
f-calls/iter3 (Floyd's)
Phases3 (detect, μ, λ)

Log