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.
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.
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.
Input: head = [1], pos = -1
Output: null
Explanation: No cycle in the list.
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.
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.