Cycle Detection

How It Works

Floyd's cycle detection sends two pointers from the head: slow advances one node per step, fast advances two. If the list terminates in null, fast reaches it and there is no cycle. If a cycle exists, both pointers eventually orbit inside it, and because fast gains one node on slow each step, it must catch slow within one lap — they meet in O(n) steps.

To locate the cycle's entry, reset one pointer to the head after the meeting and advance both one step at a time; they meet exactly at the cycle's start. This follows from the distance algebra: the head-to-entry distance is congruent to the meeting-point-to-entry distance around the loop. The whole procedure uses O(1) space, beating the hash-set approach's O(n) memory.

Step-by-Step Visualization

Code

static ListNode detectCycle(ListNode head) {
  ListNode slow = head, fast = head;

  while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow == fast) {
      slow = head;
      while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
      }
      return slow; // Cycle start
    }
  }
  return null;
}

Tips & Gotchas

Practice Problems

• 1Linked List Cycle
• 2Linked List Cycle II
• 3Find the Duplicate Number
• 4Happy Number

About the Fast & Slow Pointers Pattern

Two pointers traverse the list at different speeds. The fast pointer moves 2 nodes per step, the slow pointer moves 1. This simple idea solves cycle detection (they'll meet inside the cycle) and midpoint finding (when fast reaches end, slow is at middle).

Common Linked List Interview Problems

• Reverse Linked List
• Merge Two Sorted Lists
• Linked List Cycle
• Remove Nth Node From End
• LRU Cache
• Reorder List

Frequently Asked Questions

Other Fast & Slow Pointers Techniques