/**
* Definition for singlylinked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(!head) return NULL;
ListNode *p1=head;
ListNode *p2=head;
int count=0; //using count to record the length of cycle, if it exists.
while(p1&&p2){
count++;
p1=p1>next;
p2=p2>next;
if(p2!=NULL) p2=p2>next;
if(p1==p2&&p1&&p2){
p1=head;
p2=head;
//make the distance between p1 and p2 be the length of cycle
//when p1 and p2 meet at the first time, this postion will be the start node of the cycle.
for(int i=0;i<count;i++) p2=p2>next;
while(p1!=p2){
p1=p1>next;
p2=p2>next;
}
return p1;
}
}
return NULL;
}
};
Straight Forward C++ Solution with Explanation by using 2Pointers (16ms)


I'm having the same question and I keep having trouble understanding the reply:
Let the list be represented as 2 segments: an arbitrary length m and a section of length n, where the cycle begins at index m.
After slow has reached m, it takes another arbitrary k steps for slow to meet fast again. By now slow has traveled m+k steps, meets fast at position m+t where t is in range of 0...n1. At the same time fast has travelled 2m+2k steps.
According to the code above, the difference should be m+k steps. After the second loop when they meet again, why will they meet at the beginning of the loop?