How to detect a loop in a linked list in C++

How to detect a loop in a linked list in C++: This program will tell us how to detect a loop in a linked list in C++. Those of you who don’t know what is a linked list:  Singly Linked Lists in C++. A linked list is basically a list that stores its elements in non-contiguous locations.

The node elements in the list contain two parts :

  • Data
  • Pointer to the next node

The data part holds whatever data we store in it. And the pointer in C++ stores the location to the next node. This helps the computer to understand the location of the next data item. The pointer part of the last node is NULL which indicates the end of the list.

We will have to check that are we having a loop in this linked list or not? To check so we will have to check if there is any previous node pointing to the same node as the current node is pointing. (Also note that if there is an inner loop then it will serve as an infinite loop since no NULL statement will be encountered and hence  the traversing won’t end).

Detect a loop in a linked list in C++

Example 1:
Input: The linked list:  2->6->4->7->9->NULL
Output: There is no loop in the linked list.

Example 2:

Input : The linked list: 2->4->6->2->4->6->2->4->6->... 
Output : There is a loop present in the list.

To realize this concept we will use Floyd’s Cycle-Finding Algorithm. This concept works on the basis that one traversal will move twice as fast the other one and if the two meet at some point then there is a loop. If the algorithm detects a NULL pointer then it will stop meaning there is no loop.

Algorithm of the above program:

  1. Set two nodes as the head of the linked list.
  2. Begin while(firstnode!=NULL and secondnode->next!=NULL )
  3. firstnode=firstnode->next
  4. secondnode=secondnode->next->next
  5. check if(firstnode==secondnode) then
  6. return true
  7. end if
  8. end while
  9. return false

C++ Program: Detect a loop in a linked list

#include<iostream>
using namespace std;
    struct Node         
    {
        int data;       
        Node *next;     
        
    };
   int main()
    {
        int flag=0;
        struct Node* newnode1 = (struct Node*) malloc(sizeof(struct Node)); //making objects or nodes of the linked list
        struct Node* newnode2 = (struct Node*) malloc(sizeof(struct Node)); 
        struct Node* newnode3 = (struct Node*) malloc(sizeof(struct Node));  
        struct Node* newnode4 = (struct Node*) malloc(sizeof(struct Node)); 
        struct Node* newnode5 = (struct Node*) malloc(sizeof(struct Node)); 
        struct Node* newnode6 = (struct Node*) malloc(sizeof(struct Node));  
        struct Node* newnode7 = (struct Node*) malloc(sizeof(struct Node)); 
        struct Node* firstnode = (struct Node*) malloc(sizeof(struct Node));  
        struct Node* secondnode = (struct Node*) malloc(sizeof(struct Node));
        
        newnode1->data=1;
        newnode2->data=2;
        newnode3->data=3;
        newnode4->data=4;
        newnode5->data=5;
        newnode6->data=6;
        newnode7->data=7;
          
         //////////////////////////////
         //we are providing no loop here
        newnode1->next=newnode2;      
        newnode2->next=newnode3;
        newnode3->next=newnode4;
        newnode4->next=newnode5;      
        newnode5->next=newnode6;
        newnode6->next=newnode7;
        newnode7->next=NULL;
      
      
        firstnode=newnode1;
        secondnode=newnode1;
        while(firstnode!=NULL&&secondnode->next!=NULL)
        {
            firstnode=firstnode->next;
            secondnode=secondnode->next->next;
            if(firstnode==secondnode)
            {
                flag=1;
                cout<<"The linked list contains a loop\n";
                break;
            }
            
        }
        if(flag==0)
        cout<<"There is no loop in the linked list\n";
        
        ////////////////////////////////////////
        //we are providing a loop here
        
        newnode1->next=newnode2;      
        newnode2->next=newnode3;
        newnode3->next=newnode4;
        newnode4->next=newnode5;      
        newnode5->next=newnode6;
        newnode6->next=newnode1;     //the node points to the head node again
        newnode7->next=NULL;
      
      
        firstnode=newnode1;
        secondnode=newnode1;
        while(firstnode!=NULL&&secondnode->next!=NULL)
        {
            firstnode=firstnode->next;
            secondnode=secondnode->next->next;
            if(firstnode==secondnode)
            {
                flag=1;
                cout<<"\nThe linked list contains a loop";
                break;
            }
            
        }
        if(flag==0)
        cout<<"There is no loop in the linked list";
        
    }

The output of the above program:

detect a loop in a linked list in C++

This is a very simple program. I tried my best to do it in the easiest way possible. Hope you like it. If you have any doubts, please comment below.

Leave a Reply

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