class Solution(object): def detectCycle(self, head): slow, fast = head, head while True: if fast == None or fast.next == None: return None slow = slow.next; fast = fast.next.next if slow == fast: break while head != fast: head = head.next; fast = fast.next return head
I understand the detection part, but
why can you make sure that when node head == node fast, it is the start of the linked list cycle?
Let's say, the first node is node 0, the cycle starts at node L, and the length of the cycle is C;
Moreover, after t steps, fast catches slow.
Now we know that fast totally traveled 2t nodes, and slow traveled t nodes
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 n times.
So, if we travel L more steps at time t, then we get the start of the cycle.
However, how can we travel exactly L step?
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.
Hope that help :)
@LostSummer233 Thank you. This is very helpful
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.