Fast and Slow Pointers

Detecting cycles in a linked list seems like it would require storing all visited nodes. But there's a technique called fast and slow pointers (Floyd's Cycle Detection) that does it with O(1) space. When I first saw it, I couldn't believe how elegant it was.

The Problem

I had a linked list and needed to know if it contained a cycle. A cycle happens when a node points back to a previous node, creating an infinite loop. At first, I thought I'd need to store all visited nodes, which would use O(n) space.

My First Attempt

I used a Set to track 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
}

This worked, but I was using O(n) extra space. I wondered if there was a way to do it with O(1) space.

The Aha Moment

Then I learned about the fast and slow pointers technique. The idea is brilliant:

• Use two pointers moving at different speeds
• If there's a cycle, the fast pointer will eventually "lap" the slow pointer
• If there's no cycle, the fast pointer will hit null first

It's like two runners on a track. If there's a loop, the faster runner will catch up to the slower one!

My Solution

function hasCycle(head) {
  if (head === null || head.next === null) {
    return false; // Can't have a cycle with 0 or 1 nodes
  }

  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
}

Why This Works

The mathematical intuition: if there's a cycle of length C, and the slow pointer is at position S while fast is at position F, then:

• After each step, the distance between them changes
• Eventually, if there's a cycle, fast will catch up to slow
• If there's no cycle, fast reaches null first

Real-World Applications

I was surprised to learn this technique is used in real systems:

• Symlink verification: Detecting circular symbolic links in file systems
• Compiler dependency checking: Finding circular dependencies between modules

What I Learned

This technique taught me that sometimes the most elegant solutions come from thinking about the problem differently. Instead of storing state, I used the structure of the problem itself (the cycle) to detect it.

Key Takeaways

• Fast and slow pointers can detect cycles in O(n) time and O(1) space
• The technique works because cycles create a "catch-up" scenario
• This pattern appears in many cycle detection problems
• Sometimes the problem structure itself provides the solution

I love how this technique turns a space problem into a pure time problem. It's one of those solutions that makes you go "wow, that's clever!"