# 12ms C++ solution and explanation of Floyd Cycle algorithm

• Finding start of the cycle in a linked list, if any exists :

``````ListNode *detectCycle(ListNode *head) {
bool flag = false;
while(fast && fast->next && fast->next->next){
fast = fast->next->next;
slow = slow->next;
if(fast == slow){
flag = true;
break;
}
}
if(!flag)
return NULL;
while(slow != fast){
slow = slow->next;
fast = fast->next;
}
return slow;
}
``````

So this works because, if there exists a cycle in the linked list, the fast and slow pointer will surely meet atleast once, when the fast pointer has traversed an entire loop at least once.

So, let us say,

• the straight path before the cycle in the linked list is of length :
x
• the place where slow and fast meet is y distance from the start of
the cycle
• there are z steps left to reach the start of the cycle again from the
meeting place

slow pointer :

travels `x + y` distance to meet the fast pointer

fast pointer :

travels `(x + y + (z + y))` distance to meet the slow pointer [reason : `(x + y)` to reach the meeting place, but it again goes around the loop and meets it on its way back, so `(z + y)` steps are needed]

But the fast pointer travels at speed 2 times that of slow pointer

So, `2(x + y) = (x + 2y + z)`
`=> x = z`

This is an extremely powerful result, which means that the distance between the start of the linked list and the start of the cycle, x is equal to the distance between the start of the cycle and the meeting point, z.

So, if slow walks at a step of 1 each time from the head of the list, and if fast walks at a pace of 1 step each time. They are to meet at the start of the cycle, because slow will travel x steps and fast will travel z steps.

Size of the loop :

``````int lengthCycle(ListNode *head) {
bool flag = false;
while(fast && fast->next && fast->next->next){
fast = fast->next->next;
slow = slow->next;
if(fast == slow){
flag = true;
break;
}
}
if(!flag)
return 0;
int steps = 1;
fast = fast->next;
while(slow != fast){
fast = fast->next;
steps ++;
}
return steps;
}``````

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