# 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 in the linked list 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 in the linked list using hashing method** **is as follows:**

```
/* C++ Program to detect and remove 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 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 in the linked list by Floyd’s loop detection algorithm:**

The steps required to detect and remove loop in the 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 in the linked list 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.**