7.10 Linked List Cycle II

7.10.1 Problem Metadata

7.10.2 Description

Return the node where the cycle begins, or null if none.

7.10.3 Solution - Floyd’s Cycle Detection with Entry Point

7.10.3.1 Walkthrough

This problem extends Floyd’s cycle detection to find where the cycle starts. After detecting a cycle (when slow and fast meet), reset one pointer to head and move both pointers one step at a time. They will meet at the cycle’s entry point.

Mathematical proof: Let a be the distance from head to cycle start, and b be the distance from cycle start to meeting point. When they meet, slow traveled a + b steps, fast traveled 2(a + b) steps. The difference a + b equals the cycle length c. So a = c - b, meaning the distance from head to cycle start equals the distance from meeting point to cycle start (going forward in the cycle).

7.10.3.2 Analysis

  • Time Complexity: O(n) - Two traversals at most
  • Space Complexity: O(1) - Only pointer variables used

7.10.3.3 Implementation Steps

  1. Use Floyd’s algorithm to detect if a cycle exists and find the meeting point.
  2. If no cycle, return null.
  3. Reset one pointer (ptr) to head, keep slow at meeting point.
  4. Move both one step at a time until they meet - that’s the cycle entry.

7.10.3.4 Code - Java

public 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) {
            ListNode ptr = head;
            while (ptr != slow) {
                ptr = ptr.next;
                slow = slow.next;
            }
            return ptr;
        }
    }
    return null;
}