Fast and Slow Pointers

Detecting a cycle in a linked list does not require storing every visited node. Floyd's fast and slow pointer method uses two references and O(1) extra space. I did not expect two references to be sufficient when I first saw the method.

Detecting cycles without a set

A cycle exists when a node points back to an earlier node, so following next links never reaches null. The task is to return true for a cycle and false for a list that terminates. I first used a Set to record visited nodes:

function hasCycleNaive(head) {
  let seen = new Set();

  while (head !== null) {
    if (seen.has(head)) {
      return true; // Found a cycle!
    }
    seen.add(head);
    head = head.next;
  }

  return false; // No cycle
}

The set based method is correct, but the set grows with the list, so the extra space is O(n).

Floyd's two pointer method

I then learned the fast and slow pointers technique. One pointer moves one node at a time, while the other moves two. If the list ends, fast or fast.next reaches null. If the list loops, both pointers enter the cycle, and the faster pointer eventually catches the slower one. The implementation is:

function hasCycle(head) {
  if (head === null || head.next === null) {
    return false; // An empty list or a null next link cannot form a cycle
  }

  let slow = head; // Moves 1 step at a time
  let fast = head.next; // Moves 2 steps at a time

  while (fast !== null && fast.next !== null) {
    if (slow === fast) {
      return true; // They met! There's a cycle
    }
    slow = slow.next; // Move slow pointer 1 step
    fast = fast.next.next; // Move fast pointer 2 steps
  }

  return false; // Fast pointer hit null, no cycle
}

Once both pointers are inside a cycle, their positions repeat modulo the cycle length. The fast pointer gains one node on the slow pointer per iteration, so their relative distance eventually becomes zero. The null checks handle lists with no cycle before either pointer is dereferenced.

Complexity and applications

I was surprised to learn that the same idea is useful outside linked lists:

• Symlink verification: Detecting circular symbolic links in file systems
• Compiler dependency checking: Check for cycles when each module in the sequence has a single next dependency

The pointer loop takes O(n) time. It uses O(1) extra space. The algorithm uses the cycle itself instead of a separate visited set.

Fast and slow pointers are a useful default whenever a sequence may loop and each step can be computed from the current position. They replace O(n) visited state storage with a constant number of pointers.