Description: You are given a pointer to head node of a linked list. Your task is to detect whether a loop is present in the linked list or not.

 

If video does not load, Click here

Algorithm

Using the Floyd’s Cycle Algorithm:

•       Initialize a slow pointer and fast pointer

•       Move the slow pointer one step and fast pointer two steps in a loop until slow pointer and fast pointer point to the same node

C Implementation

 
/* Link list node */
struct node
{  int data;
  struct node* next;
};
 
/* Function to detect the loop */
int detectloop(struct node *list)
{ /* Initialize a slow pointer and fast pointer */
  struct node  *slow_p = list, *fast_p = list;
/*Move the slow pointer one step and fast pointer two steps in a loop until slow pointer and fast pointer point to the same node
*/
  while(slow_p && fast_p &&  fast_p->next )
  {
    slow_p = slow_p->next;
    fast_p  = fast_p->next->next;
    if(slow_p == fast_p)
    {
       printf("Found Loop");
       return1;
    }
  }
  return 0;
}

 

Time Complexity:

O(n)

Auxiliary Space:

O(1)

 
Go to top