Linked List Cycle II

Share

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null. Do not modify the linked list.

Example 1
Input: head = [3, 2, 0, -4], pos = 1
Output: Node with value 2
Explanation: The cycle starts at node index 1 (value = 2). The tail connects to this node.
Example 2
Input: head = [1, 2], pos = 0
Output: Node with value 1
Explanation: The tail connects back to the head; the cycle start is the head node.
Example 3
Input: head = [1], pos = -1
Output: null
Explanation: No cycle in the list.

Solution Approach - Floyd's Cycle Detection

This is a two-phase algorithm based on Floyd's Tortoise and Hare:

Phase 1 - Detect the cycle: Move slow one step and fast two steps per iteration. If they meet, a cycle exists.

Phase 2 - Find the cycle start: After the meeting point is found, reset one pointer to head. Move both pointers one step at a time. The point where they meet again is the start of the cycle.

Why does Phase 2 work? Let F = distance from head to cycle start, C = cycle length, and a = distance from cycle start to meeting point. At the meeting point: slow traveled F + a, fast traveled F + a + n*C for some integer n. Since fast moves twice as far: 2(F+a) = F+a+nC, giving F = nC - a. So moving F steps from head lands at the cycle start, and moving F steps from the meeting point also lands at the cycle start.

  • Use fast and slow pointers to find the meeting point inside the cycle.
  • If fast reaches null, return null (no cycle).
  • Reset one pointer to head; advance both one step at a time until they meet.
  • The meeting point is the cycle start node.
Java
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class LinkedListCycleII {

    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        // Phase 1: detect if cycle exists
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                // Phase 2: find cycle start
                ListNode pointer = head;
                while (pointer != slow) {
                    pointer = pointer.next;
                    slow = slow.next;
                }
                return pointer; // cycle start node
            }
        }
        return null; // no cycle
    }
}
Complexity Analysis:

Time complexity: O(n) where n is the number of nodes. Both phases together traverse the list a constant number of times.
Space complexity: O(1) as only two pointers are maintained.