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.
The problem it solves
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.
Two different problems with the same name
Cycle detection means something different depending on the structure, and the algorithms are unrelated.
In a linked list — does the chain of next pointers loop back on itself? Solved by Floyd's tortoise and hare in O(1) space.
In a graph — is there a path from some vertex back to itself? Solved by DFS, and the method differs between directed and undirected graphs.
Both matter, and confusing them wastes time. The graph case is the one with the subtlety.
Floyd's algorithm for linked lists
Move one pointer one step at a time and another two steps. If a cycle exists the fast pointer laps the slow one and they meet; if not, the fast one reaches the end.
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow is fast:
return True
return False
Why they must meet: once both are inside the cycle, the gap between them decreases by exactly one position per step, so it reaches zero. It cannot be stepped over.
Finding the cycle's entry point uses a second phase that looks like a trick and follows from the distances:
def cycle_start(head):
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow is fast: # they met inside the cycle
slow = head
while slow is not fast: # advance both one step
slow, fast = slow.next, fast.next
return slow # the entry point
return None
O(n) time, O(1) space. The alternative — storing every visited node in a set — is also O(n) time and uses O(n) space, so Floyd's algorithm is the one to know when memory matters.
Directed graphs need three states
The subtlety that catches people. In a directed graph, a two-state visited set is insufficient:
WHITE, GREY, BLACK = 0, 1, 2 # unvisited, on the current path, finished
def has_cycle_directed(graph):
colour = {n: WHITE for n in graph}
def visit(u):
colour[u] = GREY
for v in graph.get(u, []):
if colour[v] == GREY: # back edge to the current path
return True
if colour[v] == WHITE and visit(v):
return True
colour[u] = BLACK
return False
return any(visit(n) for n in graph if colour[n] == WHITE)
The distinction is between meeting a grey vertex and a black one.
Grey means the vertex is on the path currently being explored — an edge to it closes a loop. That is a cycle.
Black means the vertex and everything below it is finished. An edge to it is a cross edge or forward edge, reachable by two different routes, which is not a cycle.
Using one visited set treats both as cycles, and reports cycles in perfectly acyclic graphs — a diamond shape A→B, A→C, B→D, C→D would be falsely flagged.
Two pointers against a hash set, and why the tortoise catches up
Floyd's cycle detection is the algorithm people remember as a trick. It is not: the meeting is forced by arithmetic, and the second phase -- finding where the cycle begins -- follows from the same equation. Both halves can be watched happening.
example_01.pyPython
class Node:
def __init__(self, val):
self.val, self.next = val, None
def build(values, cycle_at):
nodes = [Node(v) for v in values]
for a, b in zip(nodes, nodes[1:]):
a.next = b
if cycle_at is not None:
nodes[-1].next = nodes[cycle_at]
return nodes[0], nodes
head, nodes = build(list("ABCDEFGH"), 3) # H points back to D
print("list: A B C D E F G H, and H -> D")
print("so the tail is A B C and the cycle is D E F G H (length 5)")
def floyd(head, verbose=False):
slow = fast = head
steps = 0
while fast and fast.next:
slow, fast = slow.next, fast.next.next
steps += 1
if verbose:
print(" step %d: slow at %s, fast at %s" % (
steps, slow.val, fast.val))
if slow is fast:
return slow, steps
return None, steps
print()
print("phase 1 -- move slow by 1, fast by 2:")
meet, steps = floyd(head, verbose=True)
print(" they met at %s after %d steps" % (meet.val, steps))
# The fast pointer gains exactly one position per step. Once both are
# inside the cycle, the gap between them shrinks by one each step, so it
# reaches zero in at most (cycle length) steps. It cannot be jumped over,
# because the gap changes by exactly one. That is the whole proof -- there
# is nothing to intuit.
def find_start(head, meet):
a, b = head, meet
steps = 0
while a is not b:
a, b = a.next, b.next
steps += 1
return a, steps
start, steps2 = find_start(head, meet)
print()
print("phase 2 -- reset one pointer to the head, advance both by 1:")
print(" they met at %s after %d steps, and that is the cycle entrance"
% (start.val, steps2))
# Why that works: let the tail be length T and the meeting point be K
# nodes into the cycle. When they met, slow had walked T + K and fast had
# walked twice that, and the difference is a whole number of laps. The
# algebra leaves T = (laps - 1) * cycle + (cycle - K) -- which is to say,
# walking T steps from the head and T steps on from the meeting point both
# land on the entrance. Here T = 3, and it took 3 steps.
print()
print(" tail length T =", steps2)
# The obvious alternative is a hash set of visited nodes:
def with_set(head):
seen, node = set(), head
while node:
if id(node) in seen:
return node
seen.add(id(node))
node = node.next
return None
print()
print("hash set finds the entrance directly:", with_set(head).val)
# Same answer, one pass, simpler code -- and O(n) memory. Floyd's uses two
# pointers and nothing else. On a linked list of a hundred million nodes
# that is the difference between a few bytes and several gigabytes, which
# is the only reason to prefer the harder algorithm.
clean, _ = build(list("ABCDE"), None)
print()
print("on an acyclic list, Floyd returns:", floyd(clean)[0])
print("and the set version returns: ", with_set(clean))
# Both correctly report no cycle. The loop condition `fast and fast.next`
# is what makes that safe: an odd-length list would otherwise step off the
# end, which is the usual bug in a hand-written version.
Output
Things to try
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.
What to remember
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.
Undirected graphs are different again
In an undirected graph, every edge appears in both directions, so DFS immediately sees an edge back to the vertex it came from. That is not a cycle — it is the same edge.
So the check is: a cycle exists if DFS reaches an already-visited vertex that is not the immediate parent.
def has_cycle_undirected(graph):
visited = set()
def visit(u, parent):
visited.add(u)
for v in graph[u]:
if v == parent:
continue # the edge we arrived on
if v in visited or visit(v, u):
return True
return False
return any(visit(n, None) for n in graph if n not in visited)
Union-Find is the cleaner alternative for undirected graphs: process each edge and attempt a union. If both endpoints are already in the same set, the edge closes a cycle. That is exactly the check inside Kruskal's algorithm.
Structure
Method
Space
Linked list
Floyd's fast/slow pointers
O(1)
Directed graph
DFS with three colours
O(V)
Undirected graph
DFS ignoring the parent, or Union-Find
O(V)
Undirected, edges arriving one at a time
Union-Find
O(V)
Note also that a parallel edge (u—v twice) or a self-loop is a cycle in an undirected graph, and the parent check above will miss the parallel-edge case unless edge identities are tracked.
Where cycle detection matters
Deadlock detection. A cycle in the wait-for graph — A waits for a lock held by B, which waits for one held by A — is a deadlock. Databases detect exactly this and abort one transaction.
Dependency validation. Build systems, package managers and module loaders reject circular dependencies, and the error message comes from this algorithm.
Spreadsheet circular references. The #REF! circular error is a detected cycle in the cell dependency graph.
Topological sorting. A cycle means no valid ordering exists, and detecting it is part of the sort.
Garbage collection. Reference cycles are why reference counting alone leaks, and Python's cycle collector exists to find them.
Infinite loop prevention in graph traversal, state machines and crawlers.
Fraud detection. Circular transaction flows between accounts.
The deadlock case is the clearest example of it running constantly in production: every relational database periodically checks its wait-for graph for cycles.
Complexity and practical notes
Both graph methods are O(V + E) — every vertex and edge examined once.
Three implementation notes:
Recursion depth. DFS-based detection on a long chain exceeds Python's limit around 1,000 frames. Convert to an iterative version with an explicit stack, tracking which vertices are on the current path.
Disconnected graphs. Start from every unvisited vertex, or cycles in later components are missed.
Self-loops. An edge from a vertex to itself is a cycle, and some implementations skip it by accident when comparing against the parent.
For very large graphs where recursion is impractical, Kahn's topological sort is often the better cycle detector: if the output contains fewer vertices than the graph, a cycle exists. It is iterative, O(V+E), and needs no colour bookkeeping.
Questions people ask
Why three colours for directed graphs? To distinguish an edge back to the current path (a cycle) from an edge into an already-finished subtree (not a cycle).
Why does the undirected case need a parent check? Because every undirected edge is stored twice, so DFS immediately sees the edge it arrived on.
Can I use Union-Find for directed graphs? No — it models symmetric connectivity and has no notion of direction.
Is Floyd's algorithm only for linked lists? It works for any functional graph where each node has exactly one successor — including iterated functions, which is how it is used in Pollard's rho factorisation.
What is the simplest way to detect a cycle in a DAG candidate? Run Kahn's topological sort; a short output means a cycle.
How do I find the cycle itself, not just detect it? Keep the current path on a stack; when a grey vertex is met, the cycle is the portion of the stack from that vertex onwards.
Recap in one screen
Linked lists: Floyd's fast and slow pointers, O(1) space, with a second phase finding the entry point.
Directed graphs: DFS with three colours — a grey vertex means a cycle, a black one does not.
Undirected graphs: DFS ignoring the parent edge, or Union-Find where a failed union means a cycle.
Both graph methods are O(V+E), and Kahn's topological sort is a convenient iterative alternative.
It runs in production constantly: deadlock detection, dependency validation and circular references.
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
# Two cycle problems that look alike and are not.
# --- 1. A linked list: Floyd's tortoise and hare, O(1) memory -----------
class Node:
def __init__(self, value):
self.value = value
self.next = None
values = [1, 2, 3, 4, 5, 6]
nodes = [Node(v) for v in values]
for a, b in zip(nodes, nodes[1:]):
a.next = b
nodes[-1].next = nodes[2] # 6 points back at 3 - a loop
def find_cycle(head):
slow = fast = head
step = 0
while fast and fast.next:
slow = slow.next # one step
fast = fast.next.next # two steps
step += 1
print(f" step {step}: slow={slow.value} fast={fast.value}")
if slow is fast: # identity, not equality
break
else:
return None
# Second phase: the distance from head to the entry equals the
# distance from the meeting point to the entry.
entry = head
while entry is not slow:
entry, slow = entry.next, slow.next
return entry
print("linked list:")
entry = find_cycle(nodes[0])
print("cycle enters at value:", entry.value if entry else "no cycle")
# --- 2. A directed graph: DFS with three colours ------------------------
graph = {"a": ["b"], "b": ["c"], "c": ["d"], "d": ["b"], "e": ["a"]}
WHITE, GREY, BLACK = 0, 1, 2 # unseen / on the stack / finished
def has_cycle(graph):
colour = {n: WHITE for n in graph}
stack = []
def visit(node):
colour[node] = GREY # now on the current path
stack.append(node)
for nxt in graph.get(node, []):
if colour[nxt] == GREY: # back edge to something still open
return stack[stack.index(nxt):] + [nxt]
if colour[nxt] == WHITE:
found = visit(nxt)
if found:
return found
colour[node] = BLACK # finished; safe to meet again
stack.pop()
return None
for node in graph:
if colour[node] == WHITE:
found = visit(node)
if found:
return found
return None
print()
print("directed graph:", graph)
print("cycle:", " -> ".join(has_cycle(graph)))
Output
How the code works
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.
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.
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.
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.
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.
Check yourself
0 of 3
Answer without scrolling back up.
Floyd's tortoise and hare uses how much extra memory?
That is the entire point of it. A visited set also works and is easier, but it costs memory proportional to the list.
Why does the comparison use 'slow is fast' rather than '==' ?
The question is whether the two pointers are on the same node, which is identity, not equality of contents.
Why does directed-graph cycle detection need three colours rather than a plain visited set?
With two states, any diamond shape - two paths meeting at one node - is reported as a cycle. GREY versus BLACK is what distinguishes them.
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.
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.