The Tortoise and The Hare

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) \mod k (once inside the cycle).
  5. Position of Hare: F(i) = (2i - m) \mod 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. 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
}

5. 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.