Given a linked-list as input, verify whether it contains a loop.
InputYou 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.
OutputYour 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