Part 23 of 26 in Linked List - set 02

Problem statement

Given a linked-list as input, verify whether it contains a loop.

Input

You need to write a function named "HasLoop" that will take pointer to head of a linked list as argument and return 1 if linked list has loop, 0 otherwise.

Output

Your function must return 1 if there is a loop in linked list, else it must return 0.

In order to detect a loop in a linked list, we make use of Floyd's cycle detection algorithm.

According to this algorithm, we use two pointers initialized to the head of the list. We then move one of them one step at a time and the other one two step at a time. We call the first one slow_ptr and the latter one as fast_ptr. Now if these two pointers ever meet at a node, then there exists a cycle for sure in the list. Otherwise if we reach the end of the list at any point of time, then there does not exist any cycle in the list.

You can check out more details on this algorithm here and here also.

editorial written by i_coder

```/*
Detect loop in a linked list
List could be empty also
Node is defined as
struct Node
{
int data;
struct Node *next;
}
*/
{
Node *turtle_ptr = head; // The pointer that traverse slowly
Node *hare_ptr = head; // The pointer that traverse fast
// We iterate until we reach the end of the list
while (turtle_ptr != NULL && hare_ptr != NULL &&
turtle_ptr->next != NULL)
{
// Move the slow pointer forward by one nodes
turtle_ptr = turtle_ptr->next;
// Move the fast pointer forward by 2 nodes
hare_ptr  = hare_ptr->next->next;

// If the slow pointer ans the fast pointer meet at some
//point then there is a loop
if (turtle_ptr == hare_ptr)
{
return 1;
}
}
// The loop has terminated which means the we have reached the end
// of the list, and hence there is no loop.
return 0;
}```

featured solution by i_coder