Detect Loop in a Linked List

Detect Loop in a Linked List” is one of the most important problem asked in various technical and algorithmic interviews. Here, we are given a linked list and our task is to detect whether there exists a  loop in a linked list. 

For Example, following linked list have a loop of length 3.

Linked List with a Loop

There are basically two methods to detect loop in a linked list:

  1. Using hashing.
  2. Floyd’s cycle finding algorithm.

Method 1: Using Hashing

The steps required to detect a loop in a linked list using hashing method is as follows:

  1. Create a hash map with key value as Node type and pair value as integer (it is implicitly initialized with zero).
  2. Traverse the linked list and put the node in hash map while incrementing the pair value. 
  3. If at any point the pair value becomes 2, then loop exists.
  4. Otherwise, at any time NULL is encountered, loop does not exist.

C++ Program to detect whether linked list contains loop or not is as follows:

/* C++ Program to detect loop in a linked list */
#include<bits/stdc++.h>
using namespace std;

/* structure of the Node of the Linked List */
struct node
{
    int data;
    struct node *next;
};

/* Function to Insert Node at the End of the Linked List */
void insert_end(struct node **head, int ele)
{
    /* Creating a Node */
    struct node *new_node;
    new_node = (struct node*)malloc(sizeof(struct node));
    new_node->data = ele;
    new_node->next = NULL;
    
    /* Check whether the linked list is empty or Not */
    
    /* If Linked List is Empty, then new node will become head of the List */
    if(*head == NULL)     
    {
        *head = new_node;
        return;
    }
    
    /* If linked list is not empty, then traverse the complete linked list and point the 
    pointer of the last node of the linked list to the new node of the linked list */
    struct node *temp = NULL;
    temp = (*head);
    while(temp->next != NULL)
    temp=temp->next;
    temp->next = new_node;
}

/* A Utility function to create a loop in the linked list */
void create_loop(struct node **head)
{
    struct node *temp = (*head);
    while(temp->next !=NULL)
    temp = temp->next;
    temp->next = (*head)->next;
}

/* Function to detect a loop in the linked list */
void detectLoop(struct node *head)
{
    /* Creating a HashMap of 'Node type' as Key and 'int' as pair */
    map<struct node*,int> mp;
    struct node *temp = head;
    /*
        Traverse the linked list and insert nodes in the Hashmap.
        While Inserting, check whether the node already exist or not.
        If node already exists, then there exists a loop in the linked list.
        Else, there does not exists a loop in the linked list.
    */
    while(temp!=NULL)
     {
         mp[temp]++;
         if(mp[temp]>1)
         {
             cout<<"Loop Exist\n";
             return;
         }
         temp = temp -> next;
     }
     cout<<"Loop does not Exist\n";
}
int main()
{
    struct node *head;
    head = NULL;
    /* Inserting Some Nodes in the Linked List */
    insert_end(&head,4);
    insert_end(&head,3);
    insert_end(&head,2);
    insert_end(&head,1);
    cout<<"Detecting Loop in a Linked List before creating Loop:\n";
    detectLoop(head);
    cout<<"\nIntroducing Loop in the Linked List!!\n";
    create_loop(&head);
    cout<<"\nDetecting Loop in a Linked List after creating Loop:\n";
    detectLoop(head);
}
OUTPUT:
Detecting Loop in a Linked List before creating Loop:
Loop does not Exist

Introducing Loop in the Linked List!!

Detecting Loop in a Linked List after creating Loop:
Loop Exist

Method 2: Floyd’s cycle finding algorithm

The steps required to detect a loop in a linked list using Floyd’s cycle finding algorithm are as follows:

  1. Initialize two pointers: ‘slow’ pointer and ‘fast’ pointer pointing to head of the linked list.
  2. Simultaneously, traverse the linked list by moving ‘slow’ pointer to next node and ‘fast’ pointer to next to next node.
  3. If at any point the ‘slow’ pointer meets the ‘fast’ pointer, then there exists a loop in the list.
  4. Else if the fast pointer reaches the end of the linked list(NULL), loop does not exists in the list. 

C++ Program to detect whether linked list contains loop or not is as follows:

/* C++ Program to detect loop in the linked list */
#include<bits/stdc++.h>
using namespace std;

/* Structure of the Node of the Linked List */
struct node
{
    int data;
    struct node *next;
};

/* Function to insert Node at the beginning of the Linked List */
void insert_end(struct node **head, int ele)
{
    /* Creating a new node */
    struct node *new_node;
    new_node = (struct node*)malloc(sizeof(struct node));
    new_node->data = ele;
    new_node->next = NULL;
    
    /* check whether the linked list is empty or not */
    
    /* If Linked List is empty, then new node will become the head of the linked list */
    if(*head == NULL)     
    {
        *head = new_node;
        return;
    }
    
    /* If Linked List is not empty, then traverse the complete linked list and point the pointer 
    of last node of the linked list to the new node of the linked list */
    struct node *temp = NULL;
    temp = (*head);
    while(temp->next != NULL)
    temp=temp->next;
    temp->next = new_node;
}

/* A Utility Function to Create Loop in a Linked List */
void create_loop(struct node **head)
{
    struct node *temp = (*head);
    while(temp->next !=NULL)
    temp = temp->next;
    temp->next = (*head)->next;
}

/* Function to detect a loop in the Linked List */
void detectLoop(struct node *head)
{
    /* Initialize two pointers; slow pointer which will traverse the linked list one node at a time
       and fast pointer which will traverse the linked list two nodes at a time */
    struct node *slow = head;
    struct node *fast = head;
    while(slow!=NULL && fast!=NULL && fast->next!=NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
        /* If at any time, the slow pointer and faster pointer meets, 
        then there exists a loop in the linked list  */
        if(slow == fast)
        {
            cout<<"Loop Exist\n";
            return;
        }
    }
    /* If the fast pointer reaches the end of the linked list(NULL), then there does 
    not exists a loop in the linked list*/
    cout<<"Loop does not exist\n";
}
int main()
{
    struct node *head;
    head = NULL;
    /* Inserting Some Nodes in the Linked List */
    insert_end(&head,4);
    insert_end(&head,3);
    insert_end(&head,2);
    insert_end(&head,1);
    cout<<"Detect Loop in a Linked List Before introducing loop in a Linked List:\n";
    detectLoop(head);
    cout<<"\nIntroducing Loop in the Linked List!!\n";
    create_loop(&head);
    cout<<"\nDetect Loop in a Linked List After introducing loop in a Linked List:\n";
    detectLoop(head);
}
OUTPUT:
Detect Loop in a Linked List Before introducing loop in a Linked List:
Loop does not exist

Introducing Loop in the Linked List!!

Detect Loop in a Linked List After introducing loop in a Linked List:
Loop Exist

Related Posts:

  1. Find the Length of the Loop present in the Linked List.
  2. Detect and Remove Loop from a Linked List.
  3. Segregate Even and Odd Nodes of the Linked List.
  4. Delete Complete Linked List.
  5. Delete Nth Node of the Linked List.
  6. Delete without head pointer of the Linked List.
  7. Delete All Occurrences of particular node of the Linked List.
  8. Delete Alternate Nodes of the Linked List.
  9. Delete every ‘N’ Nodes After ‘M’ Nodes of the Linked List.
  10. Remove Duplicate Nodes from an Unsorted Linked List.
  11. Remove Duplicate Nodes from a Sorted Linked List.
  12. Find Union and Intersection of Two Linked List.
  13. Merge Two Sorted Linked List.
  14. Reverse a Linked List.
  15. Reverse a Linked List Using Stack.
  16. Printing Linked List in Reverse Order without actually reversing the Linked List.
  17. Swap Adjacent Elements of the Linked List.
  18. Count All Occurrences of a Particular Node in a Linked List.
  19. Bubble Sort on Linked List.
  20. Insert a New Node at the Sorted Linked List.

You may also like...

Leave a Reply

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