Two pointers at different speeds will always meet inside a loop — and never meet without one. Floyd's tortoise and hare finds a cycle in O(n) time using O(1) memory.
Controls
slow = fast = head
while fast and fast.next:
slow = slow.next # 1 step
fast = fast.next.next # 2 stepsif slow == fast:
returnTrue# cycle!
Tortoise and Hare
step 0
Insight
Slow moves one node per step, fast moves two. Inside a loop the gap between them closes by exactly one each step — so they must eventually collide.
slow at0
fast at0
steps0
extra memoryO(1)
Complexity
TimeO(n)
SpaceO(1)
Hash-set methodO(n) space
Cycle Detection
Finding a loop without remembering where you have been.
Quick Context
Floyd's cycle detection — the tortoise and hare — determines whether a linked structure contains a loop, using two pointers moving at different speeds and constant extra memory.
The Obvious Solution and Its Cost
You could store every visited node in a hash set and check each new one. That works and is O(n) time — but it needs O(n) memory.
Floyd's algorithm achieves the same result with two integers. On a huge structure, or in an embedded system, that difference decides whether the problem is solvable at all.
Why They Must Meet
If there is no cycle, fast simply runs off the end — done, no loop.
If there is a cycle, both pointers eventually enter it. Once inside, consider the gap between them measured around the loop. Fast gains exactly one position per step, so the gap shrinks by one each time. A gap that decreases by one every step must reach zero — they cannot jump past each other.
This is the whole proof, and it is why the algorithm is guaranteed to terminate rather than merely likely to.
Finding Where the Cycle Starts
Detection is only half of it. After they meet, reset one pointer to the head and move both one step at a time. They will meet again exactly at the cycle's entry point.
The reason is arithmetic: if the tail before the loop has length μ and the meeting point sits λ steps into a loop of length L, the distances work out so that both pointers arrive at the entry simultaneously. Step through to the end of the cyclic example and watch that second phase run.
Where It Is Used
Linked list integrity — a corrupted list with a loop makes traversal hang forever.
Detecting infinite loops in state machines and iterative processes.
Finding duplicates — the classic "find the duplicate in an array of n+1 values from 1..n" problem becomes cycle detection when you treat values as next-pointers.
Cryptography — Pollard's rho algorithm for integer factorisation uses exactly this to find collisions.
Note that cycle detection in a graph is a different problem, usually solved with DFS and a recursion-stack check, or by topological sort.
Interactive Exploration Guide
Run the cyclic list. Watch fast lap the loop and close in on slow one position per step.
Note where they meet — usually not at the cycle's entry. That is why a second phase is needed.
Keep stepping. Phase two resets one pointer to the head and both walk at speed one, meeting exactly at the entry node.
Switch to the acyclic list. Fast runs off the end and the algorithm correctly reports no cycle.
Watch the memory readout: O(1) throughout. No matter how long the list, only two pointers are ever stored.
Key Takeaway
Floyd's algorithm detects a loop in O(n) time and O(1) space, because inside a cycle the gap between a one-step and a two-step pointer shrinks by exactly one each iteration and must hit zero. A second phase from the head then locates where the cycle begins.
Cheat sheet
Cycle Detection
Two pointers at different speeds will always meet inside a loop — and never meet without one. Floyd's tortoise and hare finds a cycle in O(n) time using O(1) memory.