vizlearn
Home / Algorithms

Cycle Detection

Algorithms & Data StructuresBy Updated

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 steps if slow == fast: return True # 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

Time O(n)
Space O(1)
Hash-set method O(n) space

Overview

Start a slow pointer and a fast pointer at the head. Move slow by one node and fast by two. If fast reaches None or has no next node, the list ends and has no cycle. If the pointers meet, they are inside a cycle.

Detect a meeting

Choose Structure in the visualizer and compare List with a cycle, List with no cycle, and Cycle back to the start. Use Auto-Run to watch the fast pointer catch the slow pointer. Compare node identity, not just stored values: different nodes can contain equal values.

Why they meet

Once both pointers are inside the loop, fast gains one node on slow at every step. Their distance around the cycle shrinks by one, so they must eventually land on the same node. If there is no loop, fast instead reaches the end.

Find the cycle entry

After a meeting, reset one pointer to the head. Move both one step at a time. They meet at the first node of the cycle. If the non-cyclic prefix has length μ and the cycle length is λ, the first meeting’s position in the cycle makes both pointers reach the entry after μ more steps.

Floyd’s algorithm takes O(n) time and O(1) extra space. A visited-node set also detects a loop in linear time, but stores up to n node references. Choose it when simpler debugging is more useful than saving memory.

In the classic duplicate-number problem, each array value can be treated as the next index to visit. That creates a linked structure over indices, and Floyd’s method can locate the cycle without modifying the array. The input constraints are essential for this mapping to be valid.

Graph cycle detection is a different problem: use DFS with graph-specific state, or topological sorting for directed acyclic graphs. See depth-first search and topological sort.

Common mistakes with Cycle Detection

  • Advancing fast by one: the pointers no longer close the gap at the required rate.
  • Checking values rather than nodes: equal values do not mean two pointers reference the same node.
  • Forgetting the empty-list case: check for None before accessing .next.
  • Assuming every cycle detector is interchangeable: linked-list pointers and graph edges need different state and reasoning.

Sources and next steps

Run it in Python

Two different cycle problems and the two different answers: Floyd's two pointers on a linked list, in O(1) memory, and three-colour DFS on a directed graph, which also names the cycle it found.

cycle_detection.pyPython 3
Output
How the code works
  1. slow = slow.next; fast = fast.next.nextTwo pointers at different speeds. Inside a loop the gap closes by one node per step, so if there is a cycle they must meet — and the whole thing costs two pointers of memory rather than a visited set.
  2. if slow is fast:is, not ==. The test is whether they are on the same node; two different nodes holding equal values would fool == completely.
  3. while entry is not slow: entry, slow = entry.next, slow.nextThe second phase, and the part that looks like magic. The distance from the head to the loop entry equals the distance from the meeting point to the entry, so two pointers advancing in step meet exactly there.
  4. WHITE, GREY, BLACKTwo colours are not enough for a directed graph. GREY means “on the path I am currently exploring”; BLACK means “finished, and reaching it again is fine”. Merging them reports a cycle for any diamond shape.
  5. if colour[nxt] == GREY: return ...An edge back into the current path is a cycle, by definition. The explicit stack is only there so the cycle can be printed — detection needs the colours alone.
Change one thing
  • Point nodes[-1].next at None. The loop exits through its else branch, which is what makes this a detector and not just a locator.
  • Change fast.next.next to fast.next. The two pointers now move at the same speed and never meet.
  • In the graph, drop GREY and treat any seen node as a cycle. Then add "e": ["a", "b"] — a false positive, on a graph with no cycle through e at all.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.




Predict, then reveal
About to run: switch Structure to Cycle back to the start. Before it does — what happens to the readout?
Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.
Check yourself
0 of 3
Answer without scrolling back up.
  1. Floyd's tortoise and hare uses how much extra memory?
  2. Why does the comparison use 'slow is fast' rather than '==' ?
  3. Why does directed-graph cycle detection need three colours rather than a plain visited set?





 Cheat sheet
Cycle Detection
Run Floyd's tortoise-and-hare algorithm on a linked list and find the cycle entry point in O(n) time and O(1) space.
ALGORITHMS · vizlearn.in/dsa/cycle_detection.html
More in Algorithms
AlgorithmsTopological SortAlgorithmsDijkstra's AlgorithmAlgorithmsBellman-Ford and Negative WeightsAlgorithmsA* Pathfinding Algorithm
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact