Given the head of a linked list, return the node where a cycle begins, or null if there is no cycle. Do not modify the list. In the tests, pos is the index the tail links back to (-1 for no cycle) and is not passed to your function; the judge reports the index of the node you return, or -1 for null.
- The list has 0 to 10^4 nodes
- -10^5 <= Node.val <= 10^5
- `pos` is -1 or a valid index
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
With a hash set, the first node we see twice is the cycle start, but that costs O(n) memory. Floyd's method does it in O(1). Let a be the distance from head to the cycle start, b the distance from the start to the meeting point, and c the cycle length. When slow and fast meet, fast has walked twice as far: 2(a + b) = a + b + k*c, so a = k*c - b. That means walking a steps from the meeting point lands exactly on the cycle start (it is b steps into the cycle, and k*c - b more steps completes whole laps). So a pointer from head and a pointer from the meeting point, both moving one step, meet at the start.
Algorithm
- Run slow (1 step) and fast (2 steps) from
headuntil they meet, or return null if fast reaches the end. - Set
p = headand keepqat the meeting point. - Move
pandqone step at a time untilp == q. - Return
p, the first node of the cycle.
O(n)Space: O(1)a = k*c - b proof on the whiteboard; many interviewers ask "why does resetting one pointer to head work?" rather than just the code.class Solution: def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]: slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow is fast: # distance head -> start equals distance meet -> start (mod cycle) p = head while p is not slow: p = p.next slow = slow.next return p return None # no cycle