Floyd Cycle Detection: The Tortoise and the Hare

Quick Answer

Floyd's algorithm walks two pointers through a linked list: a slow one moving one node per step and a fast one moving two. If the list has a cycle, the fast pointer eventually laps the slow one and they land on the same node. If the fast pointer reaches the end, there is no cycle. It uses O(1) extra memory, unlike a visited set.

The problem

Given the head of a linked list, does it contain a cycle? A cycle means some node's next points back to an earlier node, so a plain traversal never terminates.

The obvious fix is a set of visited nodes: walk the list, and if you see a node twice there is a cycle. It works, but it costs O(n) memory. The interview version, LeetCode 141, asks for O(1) extra space.

Floyd's cycle detection, nicknamed the tortoise and the hare, gets there with two pointers and no extra storage. It also answers the harder follow-up, where does the cycle start, and the same idea cracks the array problem known as find the duplicate number.

Cycles are not only a puzzle. A corrupted linked structure, a graph with an unexpected back-edge, or a badly built iterator can all loop forever, and catching that cheaply is a real need. The same two-pointer idea also underpins cycle detection in number sequences, such as Pollard's rho for integer factorisation. It is one of the highest-leverage algorithms to genuinely understand rather than memorise.

The tortoise and the hare

Two pointers start at the head. Each step, slow advances one node and fast advances two.

function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;   // fast lapped slow
  }
  return false;                       // fast ran off the end
}

Build 1 -> 2 -> 3 -> 4 -> 5 -> 6 with 6 pointing back to 3, then run it:

cycle detected: true | meeting node val: 5
acyclic list, cycle detected: false

The gotcha is the loop condition. You must test fast && fast.next before evaluating fast.next.next. Test only fast and an even-length list with no cycle throws when fast.next is null. Both checks, in that order, are what keep it safe.

Notice the meeting node is 5, not the cycle entrance 3. Phase one only proves a cycle exists and hands you some node inside it. Finding the actual entrance is a separate step.

Why they must meet

With no cycle, fast reaches the end and the loop exits. Nothing subtle there.

With a cycle, both pointers eventually enter the loop. Once both are inside, measure the gap between them along the direction of travel. Each step fast moves 2 and slow moves 1, so the gap shrinks by exactly 1 every step. A gap that decreases by 1 each step inside a finite loop must reach 0, and at that moment both pointers are on the same node.

Fast can never step over slow without landing on it, precisely because the gap changes by 1 and not 2. That is why the step sizes are 1 and 2, not 1 and 3, where the gap changes by 2 and the pointers can pass without touching.

How long does it take? Once slow enters the loop it needs at most one full lap before fast catches it, because the gap is at most the cycle length and closes by 1 per step. So phase one is O(n): at most the head-to-loop distance for slow to reach the cycle, then at most one cycle length more.

Finding where the cycle starts

Let F be the distance from the head to the cycle entrance and C the cycle length. When slow reaches the entrance it has taken F steps; fast has taken 2F and sits F mod C into the loop. They meet some a steps past the entrance, and the algebra reduces to F = nC - a for some integer n. In words: the head-to-entrance distance equals the meeting-point-to-entrance distance, give or take whole laps.

// after slow === fast:
let p = head;
while (p !== slow) {
  p = p.next;
  slow = slow.next;
}
return p;   // the cycle entrance

Reset one pointer to the head, move both one step at a time, and they collide at the entrance. Plug in the demo list: the entrance is node 3, so F = 2. The cycle is 3, 4, 5, 6, so C = 4. The pointers met at node 5, which is a = 2 steps past the entrance. Check: F = nC - a gives 2 = 4 - 2 with n = 1. Real run:

cycle start val: 3 | expected 3 | correct: true

The same trick: find the duplicate

Given n+1 integers each between 1 and n, exactly one value repeats. Find it without modifying the array and in O(1) space (LeetCode 287).

Read the array as a linked list: from index i, the next index is nums[i]. Every value is a valid index, and there are more slots than values, so following the links must eventually revisit an index, which is a cycle. The entrance to that cycle is the duplicated value, because two different indices point into it.

let slow = nums[0], fast = nums[0];
do {
  slow = nums[slow];
  fast = nums[nums[fast]];
} while (slow !== fast);
slow = nums[0];
while (slow !== fast) {
  slow = nums[slow];
  fast = nums[fast];
}
return slow;

[1,3,4,2,2] -> 2
[3,1,3,4,2] -> 3
[1,1]       -> 1

Note the do...while: slow and fast both start at nums[0], so a plain while would exit immediately, before either pointer moves.

Frequently Asked Questions