Linked List Cycle II
Problem
Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.
Examples
Example 1
Input: head = [3,2,0,-4], pos = 1 (tail connects to index 1)
Output: node with value 2
Explanation: The cycle begins at the node with value 2.
Example 2
Input: head = [1], pos = -1
Output: null
Explanation: No cycle.
Constraints
- •
The number of nodes is in the range [0, 10^4] - •
-10^5 <= Node.val <= 10^5
Hints
Hint 1
First detect whether a cycle exists at all using Floyd's slow/fast pointer technique — the same approach as the basic cycle-detection problem.
Hint 2
The interesting part is what happens after slow and fast meet inside the cycle: that meeting point isn't the cycle's start, but it has an exact mathematical relationship to it.
Hint 3
Try resetting one pointer to head and moving both remaining pointers one step at a time — where do they meet?
Solutions
public ListNode detectCycleBruteForce(ListNode head) {
Set<ListNode> visited = new HashSet<>();
ListNode curr = head;
while (curr != null) {
if (!visited.add(curr)) return curr; // first node we've already seen IS the cycle's start
curr = curr.next;
}
return null;
}Time: O(n) · Space: O(n)