Skip to content
Back to AlgorithmsAll lessons

Algorithms

Floyd's Cycle Detection

O(n) time — the hare catches up to the tortoise within one lap of the loop, if one exists · O(1) space, which is the whole point compared to tracking every visited item in a set.

The idea, in plain English

Picture two runners on a track. The tortoise takes one step at a time. The hare takes two steps at a time. If the track is a straight line with an end, the hare just finishes first. But if the track secretly loops back on itself, the faster hare eventually laps the tortoise. They land on the exact same spot again. That proves the track is a loop. This trick finds a loop in a linked list, a chain of items each pointing to the next, using almost no extra memory.

How it works

  1. 1Start two pointers, 'slow' and 'fast', at the head of the linked list.
  2. 2Move slow one step at a time, and move fast two steps at a time, over and over.
  3. 3If fast ever lands on the exact same item as slow, there is a loop. If fast instead reaches the end, there is no loop.

When you'd use it

Use it to detect an accidental loop in a linked list — a bug where one item's 'next' link points backward — or any 'does this chain of steps ever repeat' problem. It uses O(1) extra memory instead of tracking every visited item in a set.

Common beginner mistakes

  • Checking two steps ahead without first checking that one step ahead exists. This crashes on lists that end partway through.
  • Comparing item values instead of the actual items. Two different items can hold the same value, but a loop means revisiting the same item, not the same number.

Try it — edit and run

Click the code to edit · press ⌘/Ctrl+↵ to run

Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.

Expected output — hit Run to try it
List with cycle has a cycle? yes
List without a cycle has a cycle? no

See it in motion

Watch it lapFloyd’s cycle detectionO(n) time — the hare catches up to the tortoise within one lap of the loop, if one exists · O(1) space, which is the whole point compared to tracking every visited item in a set.
123456headSH

Both the tortoise (slow) and the hare (fast) start at the head.

1
Slow (S)
1
Fast (H)
0
Rounds
0.0s
Time
Tortoise (slow, +1)Hare (fast, +2)They meet → cycle

Not sure this is the right topic? See the learning paths → or where this leads →