The Tortoise and The Hare

The Real-World Scenario: Imagine an automated background job that processes a sequence of user actions in a state machine. A bug in the system causes State D to transition back to State B. Without knowing it, the job enters an infinite loop, consuming CPU and eventually crashing the server with an Out-Of-Memory (OOM) error. How do you detect if a sequence of events (or a Linked List) has a cycle before it crashes your system?

How do you detect if a Linked List has a cycle (a loop)?

  • Naive Approach: Use a HashSet to store visited nodes. If you see a duplicate, there’s a cycle.
  • Time: O(N)
  • Space: O(N) (Expensive!)
  • Optimal Approach: Floyd’s Cycle-Finding Algorithm.
  • Time: O(N)
  • Space: O(1)

1. The Algorithm

Imagine two runners on a track:

  1. Tortoise (Slow): Moves 1 step at a time.
  2. Hare (Fast): Moves 2 steps at a time.

If the track is a straight line, the Hare reaches the finish line first. If the track is a circle, the Hare will eventually lap the Tortoise from behind. If they meet, a cycle exists.

2. Interactive: Cycle Detector

Watch the race. Can the Hare catch the Tortoise?

Ready to race.
Slow: Node 0 Fast: Node 0

3. The Mathematical Anchor: Floyd’s Proof

Why is it guaranteed that the Hare meets the Tortoise? And why do they meet within one lap of the Tortoise?

The Convergence Proof (Algebraic)

  1. Let m be the distance from the head to the start of the cycle.
  2. Let k be the length of the cycle.
  3. Let i be the number of steps taken.
  4. Position of Tortoise: $S(i) = (i - m) \pmod k$ (once inside the cycle).
  5. Position of Hare: $F(i) = (2i - m) \pmod k$.
  6. The pointers meet when $F(i) \equiv S(i) \pmod k$.
  7. This implies $(2i - m) - (i - m) = n \cdot k$ (for some integer $n$).
  8. Simplifying gives $i = n \cdot k$. Since i can be any multiple of the cycle length k, and the Tortoise hasn’t even finished one lap when the Hare (moving twice as fast) laps it, they are guaranteed to meet.

The Entry Point Proof

Once they meet at node X:

  • Distance from head to collision: $D = m + p \cdot k + \delta$, where $\delta$ is the distance from the cycle start to X.
  • Because $i = n \cdot k$, the total distance $D$ is a multiple of $k$.
  • This means the distance from head to the cycle start is equivalent to the distance from the collision point back to the cycle start (moving forward).
  • Conclusion: If you put one pointer at head and one at collision, and move both at speed 1, they will collide exactly at the Cycle Start.

4. Step-by-Step State Anatomy

To visualize how the pointers converge, consider a list with a loop starting at node 4, and length of cycle = 6.

Iteration Slow Pointer Fast Pointer Distance Between Them (Inside Loop)
0 Node 0 (head) Node 0 (head) -
1 Node 1 Node 2 -
2 Node 2 Node 4 (Loop Start) -
3 Node 3 Node 6 -
4 Node 4 Node 8 Hare is 4 steps ahead (or 2 steps behind)
5 Node 5 Node 10 Hare is 5 steps ahead (or 1 step behind)
6 Node 6 Node 6 Collision! Distance is 0.

5. Implementation

We initialize both pointers at head.

  • If fast reaches null, the list ends (no cycle).
  • If fast == slow, there is a cycle.

Java

public boolean hasCycle(ListNode head) {
  if (head == null) return false;
  ListNode slow = head;
  ListNode fast = head;

  while (fast != null && fast.next != null) {
    slow = slow.next;       // 1 step
    fast = fast.next.next;  // 2 steps

    if (slow == fast) {
      return true; // Cycle detected
    }
  }
  return false; // Reached null
}

Go

func HasCycle(head *ListNode) bool {
  if head == nil {
    return false
  }
  slow, fast := head, head

  for fast != nil && fast.Next != nil {
    slow = slow.Next
    fast = fast.Next.Next

    if slow == fast {
      return true
    }
  }
  return false
}

6. Why does this work?

It’s math.

  • Suppose the cycle length is L.
  • The Hare is getting closer to the Tortoise by 1 step every iteration.
  • Eventually, the distance between them becomes 0 (modulo L).

It is mathematically guaranteed that they will meet within L iterations inside the cycle.

[!NOTE] Finding the Middle: You can use the same technique to find the middle of a list! When fast reaches the end, slow will be exactly at the halfway point.