The Tortoise and The Hare

[!NOTE] This module explores the core principles of Fast & Slow Pointers, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. Concept Definition

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)

The core idea is using two pointers moving at different speeds. If there is a cycle, the fast pointer will eventually “lap” the slow pointer.

---

2. Interactive Analysis

Watch the race. Can the Hare catch the Tortoise?

Has Cycle

Ready to race.

Slow: Node 0 Fast: Node 0

---

3. Intuition

The Convergence Proof

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.

---

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

Go

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
}

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. Complexity Analysis

Strategy	Time	Space	Notes
Floyd’s Algorithm	O(N)	O(1)	Guaranteed to meet within one cycle length.
Hash Set	O(N)	O(N)	Naive approach.