# Straight Forward C++ Solution with Explanation by using 2-Pointers (16ms)

• ``````/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
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){
//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;
}
};``````

• why the counter can record the length of cycle?

• p2 is moving one step faster than p1 each time.When p1 and p2 meet again, p2 is k step ahead of p1, here k is exactly the length of the circle. The count variable here is used to calculate the k.

• 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...n-1. 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?

• I think the count variable may not be equal to k. But it must be the integral multiple of k.

• Actually, count is integral multiple of loop length

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.