Given the head of a singly linked list that may contain a cycle, return the value of the node at which the cycle begins (the first node that is visited twice when walking from the head). Return None if there is no cycle. All node values are distinct.
Examples
Input: head = 1 -> 2 -> 3 -> 4 -> (back to 2)
Output: 2
Input: head = 1 -> 2 -> 3
Output: None
Constraints
0 <= number of nodes <= 10**4- Node values are distinct
- Target: O(n) time, O(1) extra space (a set of visited nodes works but uses O(n) space)
Goals
- Extend cycle detection to locate the cycle's first node
- Reason about pointer distances rather than values