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

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.

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;
  }
*/
int HasLoop(Node* head)
{
    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