Detect and Remove Loop in the Linked List

Detect and Remove Loop in the Linked List” is one of the most asked problem asked in technical and algorithmic interview. This problem is an extension of problem “Detect Loop in the Linked List”. In this problem, we need to first detect whether there exists a loop in the linked list or not. If loop exist, then we need to remove the loop from the linked list.

For example, we need to remove loop from the following linked list:

Linked List with Loop of Length ‘3’

After Removing the loop, the linked list becomes:

Linked List After Removing Loop

To do so, we have basically two methods.

  1. Detect and remove loop by hashing method.
  2. Detect and remove loop by Floyd’s loop detection algorithm (without counting).

Method 1: Detect and remove loop by hashing method:

The steps required to remove a loop from a linked list are as follows:

  1. Detect whether loop exist in a linked list or not using hash based method discussed in this post.
  2. If loop exist, then our temporary pointer will point to the beginning node of the loop. 
  3. We will traverse the entire loop and store the previous node in a temporary pointer node known as ‘prev’.
  4. We will then make pointer of ‘prev’ node, pointing to NULL.
  5. If loop does not exist, we will simply return.

C++  Program to detect and remove loop using hashing method is as follows:

/* C++ Program to detect and remove loop from 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 end 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, new node will become head of the linked list */
    if(*head == NULL)     
    {
        *head = new_node;
        return;
    }
    /* If Linked List is not empty, traverse the complete linked list and point the pointer 
    of last node of the linked list to the new node*/
    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 and remove Loop from the Linked List */
void detectAndRemoveLoop(struct node *head)
{
    map<struct node*,int> mp;
    struct node *temp = head;
    while(temp!=NULL)
    {
        mp[temp]++;
        if(mp[temp] == 2) // Loop Exist
        {
            struct node *p = temp;
            while(p->next != temp)
            {
                p = p -> next;
            }
            p->next = NULL;
            return;
        }
        temp = temp->next;
    }
}

/* Function to detect Loop in a Linked List */
void detectLoop(struct node *head)
{
    map<struct node*, int> mp;
    struct node *temp = head;
    while(temp!=NULL)
    {
        mp[temp]++;
        if(mp[temp]==2)
        {
            cout<<"Loop Exist\n";
            return;
        }
        temp = temp->next;
    }
    cout<<"Loop does not Exist\n";
}

/* Function to Print Linked List */
void print(struct node *head)
{
    struct node *temp = head;
    while(temp!=NULL)
    {
        cout<<temp->data<<" ";
        temp=temp->next;
    }
}
int main()
{
    struct node *head;
    head = NULL;
    /* Insert Some Nodes in the Linked List */
    insert_end(&head,4);
    insert_end(&head,3);
    insert_end(&head,2);
    insert_end(&head,1);
    /* Call Utility Function to create Loop in a Linked List */
    create_loop(&head);
    
    /* Call function to Detect whether loop exists in the linked list or not */
    detectLoop(head);
    
    /* Call Function to remove loop from the linked list, if exists  */
    cout<<"Removing Loop, if Exist!!\n";
    detectAndRemoveLoop(head);
    
    /* After Removing Loop Again, checking wheher loop exist or not in the linked list */
    detectLoop(head);
    
    /* Print the Linked List */
    cout<<"\nThe Elements of the Linked List are:\n";
    print(head);
}
OUTPUT:
Loop Exist
Removing Loop, if Exist!!
Loop does not Exist
The Elements of the Linked List are:
4 3 2 1

Method 2: Detect and remove loop by Floyd’s loop detection algorithm:

The steps required to remove a loop from a linked list are as follows:

  1. Detect whether loop exist in a linked list or not using Floyd’s cycle detection algorithm.
  2.  If loop exists in the list, point the ‘slow’ pointer to the head of the list, then move ‘slow’ and ‘fast’ pointer as same speed.
  3.  The ‘slow’ and ‘fast’ pointers will meet at the beginning of the loop.
  4. We again traverse the list with fast pointer till the node next to fast pointer is pointing to slow pointer.
  5. Then, we will point the fast pointer to NULL.

C++ Program to detect and remove loop using Floyd’s loop detection method is as follows:

/* C++ Program to Detect and Remove Loop of 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 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 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 points the pointer
    of the last node of the linked list to the new node
    */
    struct node *temp = NULL;
    temp = (*head);
    while(temp->next != NULL)
    temp=temp->next;
    temp->next = new_node;
}

/* A Utility Function to create 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 and remove loop of the linked list */
void detectAndRemoveLoop(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) 
        {
            slow = head;
            /* The slow and fast pointer meets at beginning of the loop of the linked list*/
            while(slow!=fast)
            {
                slow = slow->next;
                fast = fast->next;
            }
            /* Traverse the loop and point the pointer of last node of loop to the NULL */
            while(fast->next!=slow)
            {
                fast = fast->next;
            }
            fast->next = NULL;
            return;
        }
    }
}

/* Function to detect whether loop exists 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]==2)
        {
            cout<<"Loop Exist\n";
            return;
        }
        temp = temp->next;
    }
    cout<<"Loop does not Exist\n";
}

/* Function to print the linked list */
void print(struct node *head)
{
    struct node *temp = head;
    while(temp!=NULL)
    {
        cout<<temp->data<<" ";
        temp=temp->next;
    }
}
int main()
{
    struct node *head;
    head = NULL;
    /* Insert some nodes of the linked list */
    insert_end(&head,4);
    insert_end(&head,3);
    insert_end(&head,2);
    insert_end(&head,1);
    /* Call Utility Function to create Loop in a Linked List */
    create_loop(&head);
    
    /* Call function to Detect whether loop exists in the linked list or not */
    detectLoop(head);
    
     /* Call Function to remove loop from the linked list, if exists  */
    cout<<"Removing Loop, if Exist!!\n";
    detectAndRemoveLoop(head);
    
    /* After Removing Loop Again, checking wheher loop exist or not in the linked list */
    detectLoop(head);
    
    /* Print the Linked List */
    print(head);
}

OUTPUT:
Loop Exist
Removing Loop, if Exist!!
Loop does not Exist
4 3 2 1

Related Posts:

  1. Detect a Loop in a Linked List.
  2. Find the Length of the Loop present in the 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. Insert a New Node at the Middle of the Linked List.
  15. Insert a New Node at the Sorted Linked List.
  16. Reverse a Linked List.
  17. Reverse a Linked List Using Stack.
  18. Printing Linked List in Reverse Order without actually reversing the Linked List.
  19. Swap Adjacent Elements of the Linked List.
  20. Count All Occurrences of a Particular Node in a Linked List.

You may also like...

Leave a Reply

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