Loop in Linked List

Given a linked list we have to check whether the list contains a loop or not.

There are many ways by which we can check. The best method to do it is using Floyd’s Cycle-Finding Algorithm.

In this algorithm we take two pointers. Move one of the pointer by one and other by two. If these two pointers meet at some node then the list contains a loop else list doesn’t contains any loop.

Program to find loop in a linked list using Floyd’s Cycle-Finding Algorithm

#include<iostream>

using namespace std;

struct Node{
    int data;
    struct Node *next;
};

void insert(struct Node **head, int data){
  
  struct Node *temp = new Node;
  temp->data = data;
  temp->next = NULL;

  if(*head == NULL)
     {*head = temp;
      return;}

    temp->next = *head;
    *head = temp;
    
}

void printList(struct Node * head){
    
    while(head!=NULL){
        cout<<head->data<<"->";
        head = head->next;
    }
    cout<<"NULL"; } 

  bool checkLoop(struct Node * head){ 

  if(head == NULL) 
     return false; 

  //we will use two pointers 

  struct Node *first = head,*second =head->next;
    
    while(first && second && second->next){
         first = first->next;
         second = second->next->next; 
        
        if(first == second)
          return true;
      
    }
    
    return false;
}

int main(){

    struct Node * head = NULL;
    insert(&head,4);
    insert(&head,5);
    insert(&head,1);
    insert(&head,9);
    printList(head);
    
    //Lets create a loop
   // head->next->next->next = head->next;
    
    if(checkLoop(head)){
        cout<<"\nLOOP PRESENT";
    }
    else
       cout<<"\nNO LOOP";
    return 0;
}

Output

9->1->5->4->NULL
NO LOOP

Leave a Reply

Your email address will not be published. Required fields are marked *