Question
Given a Linked List, how can you detect and remove a loop from that linked list efficiently?
Sample Test Cases:
Test Case 1
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.*;
//LinkedListClass and Node class
class List {
static Node head;
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 */
head = curr;
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 */
if (loopNode.next == head) {
break;
}
// If loopNode didn't reach head then try the next node after head
head = head.next;
}
/* After the end of the loop loopNode is the last node of the loop. So make next of loopNode as NULL */
loopNode.next = null;
}
// print the linked list
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();
list.head = new Node(13);
list.head.next = new Node(24);
list.head.next.next = new Node(26);
list.head.next.next.next = new Node(38);
list.head.next.next.next.next = new Node(41);
// testing by creating a loop
head.next.next.next.next.next = head.next.next;
list.detectLoop(head);
System.out.println(
"Linked List after removing loop : ");
list.print(head);
}
}
Output Screenshot
Python Code
class Node:
# Constructor for node object
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
# initialize head
def __init__(self):
self.head = None
def detectLoop(self):
slow = fast = self.head
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):
head = self.head
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
if loopnode.next == head:
break
head = head.next
# 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)
new_node.next = self.head
self.head = new_node
# function to print the linked LinkedList
def printL(self):
temp = self.head
while(temp):
print (temp.data)
temp = temp.next
# Driver code
llist = LinkedList()
llist.push(13)
llist.push(24)
llist.push(26)
llist.push(38)
llist.push(41)
# Create a loop for testing
llist.head.next.next.next.next.next = llist.head.next.next
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
head : Points to the
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 */
loopNode = head;
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;
}
/* print linked list */
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()
{
struct Node* head = newNode(13);
head->next = newNode(24);
head->next->next = newNode(26);
head->next->next->next = newNode(38);
head->next->next->next->next = newNode(41);
head->next->next->next->next->next = head->next->next;
detectLoop(head);
cout << " List after removing loop" << endl;
printL(head);
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 Node head;
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
void removeLoop(Node loop, Node head)
{
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
loopNode = head;
// set other pointer to k nodes after head
curr = 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;
}
// print the linked list
void printL(Node node)
{
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}
// Driver program
public static void main(String[] args)
{
LinkedList list = new LinkedList();
list.head = new Node(55);
list.head.next = new Node(45);
list.head.next.next = new Node(54);
list.head.next.next.next = new Node(63);
list.head.next.next.next.next = new Node(56);
// loop for testing
head.next.next.next.next.next = head.next.next;
list.detectLoop(head);
System.out.println("Linked List after removing loop : ");
list.printL(head);
}
}
Output Screenshot
Python Code
# Node class
class Node:
# Constructor
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
# Function to initialize head
def __init__(self):
self.head = None
def detectLoop(self):
slow = fast = self.head
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
loopnode = self.head
# other pointer to k nodes after head
curr= self.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)
new_node.next = self.head
self.head = new_node
# print the linked LinkedList
def printL(self):
temp = self.head
while(temp):
print (temp.data)
temp = temp.next
# Driver program
llist = LinkedList()
llist.push(55)
llist.push(45)
llist.push(54)
llist.push(63)
llist.push(41)
# Create a loop for testing
llist.head.next.next.next.next.next = llist.head.next.next
llist.detectLoop()
print ("after removing loop")
llist.printL()
Output Screenshot
C++ Code
#include <bits/stdc++.h>
using namespace std;
/* Linked list node */
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
loopnode = head;
// And the other pointer to k nodes after head
curr= 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;
}
/* print linked list */
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()
{
struct Node* head = newNode(55);
head->next = newNode(45);
head->next->next = newNode(54);
head->next->next->next = newNode(63);
head->next->next->next->next = newNode(56);
/*loop for testing */
head->next->next->next->next->next = head->next->next;
detectLoop(head);
cout << "List after removing loop \n";
printL(head);
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.*;
class LinkedList {
static Node head; // head of list
/* 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
new_node.next = head;
//set the value of head node as new_node
head = new_node;
}
// print the linked list
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 {
set.add(h);
prev = h;
h = h.next;
}
}
return false;
}
/* Driver program */
public static void main(String[] args)
{
LinkedList llist = new LinkedList();
llist.push(55);
llist.push(45);
llist.push(54);
llist.push(63);
/*Create loop for testing */
llist.head.next.next.next.next = llist.head;
if (removeLoop(head)) {
System.out.println("Linked List after removing loop");
llist.printL(head);
}
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
def printList(head):
curr = head
while curr:
print(curr.data, end=" —> ")
curr = curr.next
print("None")
# identify and remove cycle in a list using hashing
def removeCycle(head):
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
s.add(curr)
# 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
# construct a linked list
head = None
for i in reversed(range(1, n + 2)):
head = Node(i, head)
# insert cycle
head.next.next.next.next.next = head.next
removeCycle(head)
printList(head)
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
void printList(Node* head)
{
while (head != NULL) {
cout << head->val << " ";
head = head->next;
}
cout << endl;
}
// Function to detect and remove loop
void hashAndRemove(Node* head)
{
// hash map hashes addresses of the list nodes
unordered_map<Node*, int> node_map;
// pointer to last node
Node* last = NULL;
while (head != NULL) {
// insert node in the map
if (node_map.find(head) == node_map.end()) {
node_map[head]++;
last = head;
head = head->next;
}
// 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()
{
Node* head = newNode(55);
head->next = head;
head->next = newNode(45);
head->next->next = newNode(54);
head->next->next->next = newNode(63);
head->next->next->next->next = newNode(56);
/* loop for testing */
head->next->next->next->next->next = head->next->next;
// printList(head);
hashAndRemove(head);
printf(" List after removing loop \n");
printList(head);
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.
People are also reading:
- Minimum Edit Distance
- WAP to Count no. of alphabets, digits and spaces present in a file
- Find maximum of minimum for every window size in a given array
- WAP to Print Triangle Using * Character
- Find ancestors of a given node in a Binary Tree
- Subset Sum Problem
- Clone a Singly Linked List
- Maximum size square sub-matrices with all 1’s
- Merge Sort for Linked Lists
- Convert a Binary Tree to Doubly Linked List
