# How to find and remove loops in a Linked List?

Posted in  Vinay Khatri
Last updated on September 26, 2023

## Question

Given a Linked List, how can you detect and remove a loop from that linked list efficiently?

### Sample Test Cases:

#### Sample Input Expected Output 13-->24-->26-->38-->41-->NULL.

#### Test Case 2

Sample Input #### Expected Output

55-->45-->54-->63-->56-->NULL

#### Test Case 3

Sample Input #### Expected Output

7-->9-->8-->6-->NULL

### Explanation

As the problem states, we need to find a loop in a LinkedList and remove it. If the loop was found and successfully removed, return true and print the list after removing the loop else, if the loop was not found, return false. For example, the linked list in sample test case 1, after removing the loop should change to 13-->24-->26-->38-->41-->NULL. Before removing the loop, it is important to detect it. To detect the loop we use Floyd’s Cycle detection algorithm. To remove the loop, the pointer to the last node of the loop is required which is node 41 in the above test case. After having the pointer to the last node of the loop, we just need to set its next pointer to null. After detecting the loop, there are different methods to approach this problem. We have discussed them below.

### Naive Approach

• Floyd’s Cycle Detection Algorithm will stop when fast and slow pointers meet at a common point.
• This common point will be one of the nodes that are part of the loop.
• Store the address of this common point in a node variable named loopNode.
• Later, start from the head node of the Linked List and check whether any one of all nodes is reachable from loopNode one by one.
• Each time a reachable node will be found, that node will be the start node of the loop in the Linked List and the pointer to the node that is previous to this node can be found.

#### Java Code

```import java.lang.*;
import java.util.*;
class List {

static class Node {

int data;
Node next;

Node(int d)
{
data = d;
next = null;
}
}

//detect loop in the list
int detectLoop(Node node)
{
Node slow = node, fast = node;
while (slow != null && fast != null
&& fast.next != null) {
slow = slow.next;
fast = fast.next.next;

// If slow and fast meet at the same point then a loop is there return 1;
if (slow == fast) {
removeLoop(slow, node);
return 1;
}
}
//else return 0
return 0;
}

// remove loop
void removeLoop(Node loop, Node curr)
{
Node head = null, loopNode = null;

/* move the pointer to the beginning of the Linked List
one by one  */
while (true) {

/* Now start a pointer from node where they meet and check
if it ever reaches  loopNode*/
loopNode = loop;
while (loopNode.next != loop && loopNode.next != head) {
loopNode = loopNode.next;
}

/* If loopNode reached head then there is a loop. So
break it */
break;
}

// If loopNode didn't reach head then try the next node after head
}

/* After the end of the loop loopNode is the last node of the loop. So make next of loopNode as NULL */
loopNode.next = null;
}

void print(Node node)
{
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}

// Driver code
public static void main(String[] args)
{
List list = new List();

// testing by creating a loop
System.out.println(
"Linked List after removing loop : ");
}
}

```

Output Screenshot #### Python Code

```class Node:
# Constructor for node object
def __init__(self, data):
self.data = data
self.next = None

def __init__(self):

def detectLoop(self):
while(slow and fast and fast.next):
slow = slow.next
fast = fast.next.next

# If slow and fast meet
# then there is a loop
if slow == fast:
self.removeLoop(slow)
# Return 1 to indicate that loop if found
return 1

# Return 0 to indicate that there is no loop
return 0

# Function to remove loop
# loop node= Pointer to loop node
# head = Pointer to the start node of the linked list
def removeLoop(self, loop_node):

while(1):
# Now start a pointer from loop_node and check
# if it ever reaches loopnode
loopnode = loop_node
while(loopnode.next != loop_node and loopnode.next != head):
loopnode = loopnode.next

# If loopnode reached head then there is a loop.
# So break the loop
break

# After the end of loop loopnode is the last node of
# the loop. So make next of loopnode as NULL
loopnode.next = None

# insert a new node at the beginning
def push(self, new_data):
new_node = Node(new_data)

def printL(self):
while(temp):
print (temp.data)
temp = temp.next

# Driver code
llist.push(13)
llist.push(24)
llist.push(26)
llist.push(38)
llist.push(41)

# Create a loop for testing

llist.detectLoop()

print ("after removing loop")
llist.printL()```

Output Screenshot #### C++ Code

```#include <bits/stdc++.h>
using namespace std;

/* list node */
struct Node {
int data;
struct Node* next;
};

/* Function to remove loop.
Used by detectLoop() */
void removeLoop(struct Node*, struct Node*);

/* This function detects and
removes loop in the list*/
int detectLoop(struct Node* list)
{
struct Node *slow = list, *fast = list;

while (slow && fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;

/* If slow and fast meet then
there is a loop */
if (slow == fast) {
removeLoop(slow, list);

/* Return 1 : loop is found */
return 1;
}
}

/* Return 0 :there is no loop*/
return 0;
}

/* Function to remove loop.
loop_node : Points to
one of the loop nodes
start node of the list */
void removeLoop(struct Node* loop_node, struct Node* head)
{
struct Node* loopNode;
struct Node* curr;

/* Move the pointer to the beginning
Linked List and move it one position at a time
to get the
first node */
while (1) {
/* Now start a pointer from
loop_node and check if
it ever reaches ptr2 */
curr = loop_node;
while (curr->next != loop_node
&& curr->next != loopNode)
curr = curr->next;

/* If curr reached loopNode
then a loop is there. So
break it */
if (curr->next == loopNode)
break;

/* If curr didn't reach loopNode
then try the next node
* after loopNode */
loopNode = loopNode->next;
}

/*  at the end, curr will be the last node of the loop. So make next of curr as NULL */
curr->next = NULL;
}

void printL(struct Node* node)
{
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
}

struct Node* newNode(int key)
{
struct Node* temp = new Node();
temp->data = key;
temp->next = NULL;
return temp;
}

// Driver Code
int main()
{

cout << " List after removing loop" << endl;
return 0;
```

Output Screenshot #### Time Complexity

The time complexity for this code is O(n^2) where n is the number of nodes in the Linked List. It is O(n^2) because, for every node of the Linked List, we have to traverse the entire Linked List to check if that node is reachable from the loop node.

#### Space Complexity

The space complexity of this code is O(1) because we are not using any additional space or data structure to store the values.

### Efficient Method

• The first step of this method is the same, use Floyd’s Cycle Detection Algorithm to detect loop and get the pointer to a node belonging to the loop.
• Count the number of nodes in the loop and set the count to c.
• Set a pointer at the head and another at c’th node from the head.
• Move both the pointers at equal speed, they will meet at the starting node of the loop.
• Get the pointer to the last node of the loop and set its next pointer to null.

#### Java Code

```class LinkedList {

static class Node {

int data;
Node next;

Node(int d)
{
data = d;
next = null;
}
}

// detect loop in the list
int detectLoop(Node node)
{
Node slow = node, fast = node;
while (slow != null && fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;

// If  loop is present
if (slow == fast) {
removeLoop(slow, node);
return 1;
}
}
//if no loop
return 0;
}

// Function to remove loop
{
Node loopNode = loop;
Node curr = loop;

// Count the number of nodes in loop
int k = 1;
while (loopNode.next != curr) {
loopNode = loopNode.next;
k++;
}

// Fix one pointer to head

// set other pointer to k nodes after head
for (int i = 0; i < k; i++) {
curr = curr.next;
}

//  Move both pointers at the same pace
while (curr != loopNode) {
loopNode = loopNode.next;
curr = curr.next;
}

// Get pointer to the last node
while (curr.next != loopNode) {
curr = curr.next;
}

/* Set the next node of the loop ending node
to null*/
curr.next = null;
}

void printL(Node node)
{
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}

// Driver program
public static void main(String[] args)
{

//  loop for testing
System.out.println("Linked List after removing loop : ");
}
}```

Output Screenshot #### Python Code

```# Node class
class Node:
# Constructor
def __init__(self, data):
self.data = data
self.next = None

def __init__(self):

def detectLoop(self):

while(slow and fast and fast.next):
slow = slow.next
fast = fast.next.next

# If slow and fast meet then there is a loop
if slow == fast:
self.removeLoop(slow)

# Return 1 if a loop is found
return 1

# Return 0 if there is no loop
return 0

# Function to remove loop
# loop_node --> pointer to one of the loop nodes
# head --> Pointer to the start node of the linked list
def removeLoop(self, loop_node):
loopnode= loop_node
curr = loop_node

# get number of nodes in loop
k = 1
while(loopnode.next != curr):
loopnode = loopnode.next
k += 1

# set one pointer to head

# other pointer to k nodes after head
for i in range(k):
curr = curr.next

# Move both pointers at the same pace
while(curr != loopnode):
loopnode = loopnode.next
curr = curr.next

# Get pointer to the last node
while(curr.next != loopnode):
curr = curr.next

# Set the next node of the loop ending node to null
curr.next = None

# insert a new node at the beginning
def push(self, new_data):
new_node = Node(new_data)

def printL(self):
while(temp):
print (temp.data)
temp = temp.next

# Driver program
llist.push(55)
llist.push(45)
llist.push(54)
llist.push(63)
llist.push(41)

# Create a loop for testing

llist.detectLoop()

print ("after removing loop")
llist.printL()```

Output Screenshot #### C++ Code

```#include <bits/stdc++.h>
using namespace std;

struct Node {
int data;
struct Node* next;
};

/*  remove loop. */
void removeLoop(struct Node*, struct Node*);

/* This function detects and removes loop in the list
If loop is present returns 1,
otherwise returns 0 */
int detectLoop(struct Node* list)
{
struct Node *slow = list, *fast = list;

// loop exists or not
while (slow && fast && fast->next) {
slow = slow->next;
fast = fast->next->next;

/* If slow and fast meet  then there
is a loop */
if (slow == fast) {
removeLoop(slow, list);

/* Return 1 if loop is found */
return 1;
}
}

/* Return 0 if there is no loop*/
return 0;
}

/* Function to remove loop.
loop_node : Pointer to one of the loop nodes
head : Pointer to the start node of the linked list */
void removeLoop(struct Node* loop_node, struct Node* head)
{
struct Node* loopnode = loop_node;
struct Node* curr = loop_node;

// Count the number of nodes in loop
unsigned int k = 1;
while (loopnode->next != curr) {
loopnode = loopnode->next;
k++;
}

// Fix one pointer to head

// And the other pointer to k nodes after head
for (int i = 0; i < k; i++)
curr = curr->next;

/*  Move both pointers at the same pace,
they will meet at the loop’s starting node */
while (curr != loopnode) {
loopnode = loopnode->next;
curr = curr->next;
}

// Get pointer to the last node
while (curr->next != loopnode)
curr = curr->next;

/* Set the next node of the loop ending node
to null */
curr->next = NULL;
}

void printL(struct Node* node)
{
// Print the list after loop removal
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
}

struct Node* newNode(int key)
{
struct Node* temp = new Node();
temp->data = key;
temp->next = NULL;
return temp;
}

// Driver Code
int main()
{

/*loop for testing */

cout << "List after removing loop \n";
return 0;
}```

Output Screenshot #### Time Complexity

The time complexity of this approach is O(n).

#### Space Complexity

Since we are not using any additional space, the space complexity of this approach is O(1).

### Using Hashing

• We can also try using a HashSet.
• We insert each node in the hash set, before inserting, we check if it is already present in the hash set, if yes, we set the next of last node in the cycle as null.
• If not, we insert that node in the hash set.

#### Java Code

```import java.util.*;

/* Node*/
static class Node {
int val;
Node next;
Node(int d)
{
val = d;
next = null;
}
}

/* Inserts a new Node at front  */
static public void push(int new_data)
{

Node new_node = new Node(new_data);

//set the next of new node as head

//set the value of head node as new_node
}

void printL(Node node)
{
while (node != null) {
System.out.print(node.val + " ");
node = node.next;
}
}

// Returns true if the loop is removed else returns false.
static boolean removeLoop(Node h)
{
HashSet<Node> set = new HashSet<Node>();
Node prev = null;
while (h != null) {
// If we already have this node it means there is a cycle and we
// to remove this cycle set the next of
// the previous node with null.

if (set.contains(h)) {
prev.next = null;
return true;
}

// If we are seeing the node for
// the first time, insert it in hash
else {
prev = h;
h = h.next;
}
}

return false;
}

/* Driver program */
public static void main(String[] args)
{

llist.push(55);
llist.push(45);
llist.push(54);
llist.push(63);

/*Create loop for testing */

}
else
System.out.println("No Loop found");
}
}```

Output Screenshot #### Python Code

```# List Node
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next

# nction to print list
while curr:
print(curr.data, end=" —> ")
curr = curr.next
print("None")

# identify and remove cycle in a  list using hashing
prev = None        # previous pointer
curr = head        # main pointer

# maintain a set to store visited nodes
s = set()

# traversing  the list
while curr:
if curr in s:
prev.next = None
return

# insert the current node into the set

# update the previous pointer to the current node and
# move the main pointer to the next node
prev = curr
curr = curr.next

if __name__ == '__main__':
# total number of nodes in the linked list
n = 5

for i in reversed(range(1, n + 2)):

# insert cycle

Output Screenshot #### C++ Code

```#include <bits/stdc++.h>
using namespace std;

struct Node {
int val;
struct Node* next;
};

Node* newNode(int val)
{
Node* temp = new Node;
temp->val = val;
temp->next = NULL;
return temp;
}

//  function to print a list
{
cout << head->val << " ";
}
cout << endl;
}

// Function to detect and remove loop
{
// hash map hashes addresses of the list nodes
unordered_map<Node*, int> node_map;
// pointer to last node
Node* last = NULL;
//  insert node in the map
}
// if node present in map already, there is a cycle, make the last node's next pointer      // as NULL
else {
last->next = NULL;
break;
}
}
}
/* Driver program */
int main()
{

/* loop for testing */

printf(" List after removing loop \n");

return 0;
}```

Output Screenshot #### Time Complexity

The time complexity of this approach is O(n), where n is the number of nodes in the Linked List. Because we traverse the List entirely once while inserting each node in the Linked List.

#### Space Complexity

The space Complexity of this approach is O(n) because we are using extra space by taking the help of a Hash Set to store the nodes.

## Conclusion

To conclude, in this article, we discussed how to find and remove loops in Linked Lists through several approaches. We discussed a naive approach and two efficient approaches and discussed their respective time and space complexities as well. We hope that you will now be able to solve this question along with it’s variations successfully.