# 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 “

**”. 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.**

*Detect Loop in the Linked List*For example, we need to remove loop from the following linked list:

After Removing the loop, the linked list becomes:

To do so, we have basically two methods.

- Detect and remove loop by hashing method.
- 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:

- Detect whether loop exist in a linked list or not using hash based method discussed in this post.
- If loop exist, then our temporary pointer will point to the beginning node of the loop.
- We will traverse the entire loop and store the previous node in a temporary pointer node known as ‘prev’.
- We will then make pointer of ‘prev’ node, pointing to NULL.
- 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); }

Loop Exist Removing Loop, if Exist!! Loop does not Exist The Elements of the Linked List are: 4 3 2 1OUTPUT:

**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:

- Detect whether loop exist in a linked list or not using Floyd’s cycle detection algorithm.
- 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.
- The ‘slow’ and ‘fast’ pointers will meet at the beginning of the loop.
- We again traverse the list with fast pointer till the node next to fast pointer is pointing to slow pointer.
- 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); }

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

**Related Posts:**

**Detect a Loop in a Linked List.****Find the Length of the Loop present in the Linked List.****Segregate Even and Odd Nodes of the Linked List.****Delete Complete Linked List.****Delete Nth Node of the Linked List.****Delete without head pointer of the Linked List.****Delete All Occurrences of particular node of the Linked List.****Delete Alternate Nodes of the Linked List.****Delete every ‘N’ Nodes After ‘M’ Nodes of the Linked List.****Remove Duplicate Nodes from an Unsorted Linked List.****Remove Duplicate Nodes from a Sorted Linked List.****Find Union and Intersection of Two Linked List.****Merge Two Sorted Linked List.****Insert a New Node at the Middle of the Linked List.****Insert a New Node at the Sorted Linked List.****Reverse a Linked List.****Reverse a Linked List Using Stack.****Printing Linked List in Reverse Order without actually reversing the Linked List.****Swap Adjacent Elements of the Linked List.****Count All Occurrences of a Particular Node in a Linked List.**