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. Problem Definition

Problem Statement: Given the head of a linked list, determine if it has a cycle in it. There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer.

Constraints:

  • The number of the nodes in the list is in the range [0, 10<sup>4</sup>].
  • -10<sup>5</sup> &le; Node.val &le; 10<sup>5</sup>.

Examples:

  • Input: head = [3,2,0,-4], pos = 1 (tail connects to node index 1) Output: true
  • Input: head = [1,2], pos = 0 (tail connects to node index 0) Output: true
  • Input: head = [1], pos = -1 (no cycle) Output: false

Edge Cases & Clarifying Questions:

  • Q: Can the list be empty? A: Yes, an empty list has no cycle.

  • Q: Can the list have only one node? A: Yes, if its next pointer is null, there is no cycle. If it points to itself, there is a cycle.

2. Interactive Analysis

Watch the race. Can the Hare catch the Tortoise?

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

3. Intuition (The “Genesis”)

Brute Force Approach: The simplest way to detect a cycle is to keep track of every node we visit. We can iterate through the list and store each node in a HashSet. If we encounter a node that is already in our set, a cycle exists.

  • Time Complexity: O(N) because we visit each node at most once.
  • Space Complexity: O(N) because we need to store up to N nodes in the HashSet.

Optimized Approach (Floyd’s Cycle-Finding Algorithm): Also known as the Tortoise and Hare pattern. We can optimize the space complexity to O(1) using two pointers moving at different speeds.

  • Slow Pointer (Tortoise): Moves 1 step at a time.
  • Fast Pointer (Hare): Moves 2 steps at a time. If there is a cycle, the fast pointer will eventually “lap” the slow pointer and they will meet at the same node.

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) ≡ S(i) mod k.
  7. This implies (2i - m) - (i - m) = n · k (for some integer n).
  8. Simplifying gives i = n · 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.

Common Pitfalls:

  • Null Pointer Exceptions: Forgetting to check if fast or fast.next is null before advancing the fast pointer by two steps.

  • Returning the Meeting Node: This algorithm only detects a cycle. The node where they meet is not necessarily the start of the cycle.

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