Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.
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.
The number of nodes is in the range [0, 10^4]-10^5 <= Node.val <= 10^5First detect whether a cycle exists at all using Floyd's slow/fast pointer technique — the same approach as the basic cycle-detection problem.
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.
Try resetting one pointer to head and moving both remaining pointers one step at a time — where do they meet?
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)