142. Linked List Cycle II
Let’s say, the first node is node
0, the cycle starts at node
L, and the length of the cycle is
Now we know that fast totally traveled
2t nodes, and slow traveled
Then we have:
2t - t = nC (where
n is an positive integer.)
Now, think about that, at step
t, if we travels
L more steps, where are we?
i.e. if we travel
L+t = L + nC steps in total, where are we?
Absolutely, at the start of the cycle, because we have covered the first
L nodes once and the entire cycle
So, if we travel
L more steps at time
t, then we get the start of the cycle.
However, how can we travel exactly
The answer is to use an other pointer to travel from node
0, and when they meet together, it is exactly
L steps and both of them are at the start of the cycle.
class Solution(object): def detectCycle(self, head): """ :type head: ListNode :rtype: bool """ slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: break else: return None while head != slow: slow = slow.next head = head.next return head