To detect a cycle in a linked list, the slow and fast pointers method is used. We can easily understand this method for cycle detection, but to find a position of the cycle, its a kind of magic. There is a logic behind this magic. Great Floyed.
To detect a cycle, use 2 pointers. Initially, these 2 pointers point to head, one pointer traverses each node, another pointer traverses alternate nodes, once both the nodes meet at one node, then the cycle is detected.
To find the position of the cycle, 2 pointers are used: one initialized to head, another is a pointer pointing to the node where the cycle is detected. Traverse both the pointers to each next node, once both the pointers point to the same node, that’s the position where 2 cycle starts. This logic works for any kind of cycle.
In this example, the cycle is detected after 3 traversals, the position is detected after one more traversal. The total number of nodes is 4, the cycle started at position 1.
In this example, the total number of nodes is 6, the cycle position started at the 4th node. The cycle is detected after 3 traversals. Cycle position is detected after 3 more traversals.
In this example, the total number of nodes in the list is 7. The cycle position started at the 4th node. The cycle is detected after 4 traversals and the cycle position is detected after 3 more traversals.
The logic behind the position of cycle finding is distance. The position of the cycle is detected with the distance as the total number of nodes. Depending on the start of cycle position, the number of nodes (x) to be traversed to detect the cycle position varies. To find the position of the cycle we should traverse the total number of nodes — x nodes = y distance.
For detecting the cycle, a fast pointer initially traversed 2x positions. These 2 pointers intersected at one position assume it as x position. Now if the fast pointer moved y positions, then it reaches to starting the cycle position. These y positions are from the start of the head till the start of the cycle position.
Below is the C code segment:
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode *nxt, *dnxt;
nxt = dnxt = head;
while (dnxt != NULL){
nxt = nxt->next;
if (dnxt->next)
dnxt = dnxt->next->next;
else
return NULL;
if (dnxt == nxt)
break;
}
if (!dnxt)
return NULL;
/* find the cycle */
nxt = head;
while (dnxt != tmp)
{
dnxt = dnxt->next;
nxt = nxt->next;
}
return nxt;
}
