Problem Statement
We are given the head pointer of a linked list. Determine whether the linked list contains a loop or not. If it contains a loop, then we need to remove it as well from the given linked list.
There is a loop in a linked list if there is some node that can be reached again by continuously following the next pointer.
The loop must be removed from the linked list so that after the cycle is removed, the resulting linked list becomes linear and connected.
Example
Below is a linked list with a loop/cycle.
In the example mentioned above, if we start from the node 3, the path 3 -> 4 -> 5 -> 6 -> 3 forms a cycle. So, the linked list contains a cycle.
Below is the linked list after removing the link between the node with value 6 and the node with value 3.
Approach 1: Check One by One (code in Java, Python, C++)
In this approach, we first use Floyd’s cycle detection algorithm, which is very efficient in detecting and removing loops in a linked list. Using Floyd’s cycle detection algorithm allows us to detect and remove a loop from the linked list without using any extra space.
To find the starting point of the loop (so that we can delete the link between the starting and the ending node of the loop to remove the cycle), we can do the following.
Start from the head node of the linked list and check whether the node is reachable from the intersection point. If a node is reachable from the intersection point, this node is the starting point of the loop.
Code Implementation
Java
// class definition of the ListNode
public class ListNode{
public int val;
public ListNode next;
public ListNode(int value){
val = value;
next = null;
}
}
public class Globals{
// function to check whether the pointer head1 is reachable from the pointer sptr
public static boolean isreachable(ListNode head1, ListNode sptr){
ListNode tempNode = sptr.next;
while (tempNode != head1 && tempNode != sptr){
tempNode = tempNode.next;
}
if (tempNode == head1){
// this means that head1 is reachable from sptr
return true;
}
// this means that head1 is not reachable from sptr
return false;
}
// function to remove loop in linked list using hashing
public static void checkOneByOne(ListNode head){
// initializing sptr and fptr
ListNode sptr = head;
ListNode fptr = head;
while (sptr != null && fptr != null && fptr.next != null){
sptr = sptr.next; // moving sptr by one
fptr = fptr.next.next; // moving fptr by two
if (sptr == fptr){
// we get the intersection point
break;
}
}
if (sptr == null || fptr == null || fptr.next == null){
// this means the loop is not present in the linked list
System.out.print("Loop is not present in the linked list.");
System.out.print("\n");
}
else{
// this means the loop is present in the linked list
System.out.print("Loop is present in the linked list.");
System.out.print("\n");
// finding starting point of the loop
// initializing pointer to iterate from head
ListNode head1 = head;
// run the loop till the head1 pointer is not reachable from sptr
while (!isreachable(head1, sptr)){
head1 = head1.next;
}
// now, head1 is pointing to the start of the loop in the linked list
// removing loop
// moving sptr to the node just preceding the head1 pointer in the loop
while (sptr.next != head1){
sptr = sptr.next;
}
//Remove the link between sptr and head to remove the cycle from the linked list
sptr.next = null;
System.out.print("Loop has been removed from the linked list.");
System.out.print("\n");
}
}
}
Python
# class definition of the ListNode
class ListNode:
def __init__(self, value):
self.val = value
self.next = None
class Globals:
# function to check whether the pointer head1 is reachable from the pointer sptr
@staticmethod
def isreachable(head1, sptr):
tempNode = sptr.next
while tempNode is not head1 and tempNode is not sptr:
tempNode = tempNode.next
if tempNode is head1:
# this means that head1 is reachable from sptr
return True
# this means that head1 is not reachable from sptr
return False
# function to remove loop in linked list using hashing
@staticmethod
def checkOneByOne(head):
# initializing sptr and fptr
sptr = head
fptr = head
while sptr is not None and fptr is not None and fptr.next is not None:
sptr = sptr.next # moving sptr by one
fptr = fptr.next.next # moving fptr by two
if sptr is fptr:
# we get the intersection point
break
if sptr is None or fptr is None or fptr.next is None:
# this means the loop is not present in the linked list
print("Loop is not present in the linked list.")
else:
# this means the loop is present in the linked list
print("Loop is present in the linked list.", end = '')
print("\n", end = '')
# Finding starting point of the loop
# Initializing pointer to iterate from head
head1 = head
# run the loop till the head1 pointer is not reachable from sptr
while not Globals.isreachable(head1, sptr):
head1 = head1.next
# Now, head1 is pointing to the start of the loop in the linked list
# removing loop
# moving sptr to the node preceding the head1 pointer in the loop
while sptr.next is not head1:
sptr = sptr.next
# Removing the link between sptr and head to remove a cycle from the linked list
sptr.next = None
print("Loop has been removed from the linked list.", end = '')
print("\n", end = '')
C++
// class definition of the ListNode
class ListNode{
public:
int val;
ListNode* next;
ListNode(int value){
val=value;
next=NULL;
}
};
// function to check whether the pointer head1 is reachable from the pointer sptr
bool isreachable(ListNode* head1, ListNode* sptr){
ListNode* tempNode = sptr->next;
while(tempNode != head1 && tempNode != sptr){
tempNode=tempNode->next;
}
if(tempNode == head1){
// this means that head1 is reachable from sptr
return true;
}
// this means that head1 is not reachable from sptr
return false;
}
// function to remove the loop in the linked list using hashing
void checkOneByOne(ListNode* head){
// initializing sptr and fptr
ListNode* sptr = head;
ListNode* fptr = head;
while(sptr!=NULL && fptr!=NULL && fptr->next!=NULL){
sptr = sptr->next; // moving sptr by one
fptr = fptr->next->next; // moving fptr by two
if(sptr == fptr){
// we get the intersection point
break;
}
}
if(sptr==NULL || fptr==NULL || fptr->next==NULL){
// this means the loop is not present in the linked list
cout<<"Loop is not present in the linked list."<<endl;
}
else{
// this means the loop is present in the linked list
cout<<"Loop is present in the linked list."<<endl;
/* finding starting point of the loop */
// initializing pointer to iterate from head
ListNode* head1 = head;
//Run the loop till the head1 pointer is not reachable from sptr
while(!isreachable(head1,sptr)){
head1=head1->next;
}
//Now, head1 is pointing to the start of the loop in the linked list
/* removing loop */
// moving sptr to the node just preceding the head1 pointer in the loop
while(sptr->next != head1){
sptr=sptr->next;
}
// removing the link between sptr and head to remove the cycle from the linked list
sptr->next = NULL;
cout<<"Loop has been removed from the linked list."<<endl;
}
}
Complexity Analysis
The time and space complexity of the above approach is given below.
Time Complexity : Since for each node, we are checking whether it is reachable from the sptr node or not, the time complexity of the above approach is O(n^2).
Space Complexity : The space complexity for the above approach is O(1) since we are using only two pointers to detect the loop and no extra space.
Approach 2: Better Solution
In this approach, we find the intersection point of the slow and fast pointers using Floyd’s algorithm. Once intersected, count the nodes in the cycle starting from the slow pointer. Then, we will initiate two pointers: one from the head and another from a node ‘ctr’ distance away. Move them one node at a time until they meet; this intersection marks the start node of the loop.
This method efficiently identifies cycles in linked lists and determines their start points, ensuring optimal traversal for loop detection and node counting.
The graphical representation of how the two pointers will move in every iteration is given below.
Finally, we will remove the link between the start node and the preceding node to remove the cycle.
Code Implementation
Java
// class definition of the ListNode
public class ListNode{
public int val;
public ListNode next;
public ListNode(int value){
val = value;
next = null;
}
}
public class Globals{
// function to remove loop in linked list using hashing
public static void removeLoop(ListNode head){
// initializing sptr and fptr
ListNode sptr = head;
ListNode fptr = head;
while (sptr != null && fptr != null && fptr.next != null){
sptr = sptr.next; // moving sptr by one
fptr = fptr.next.next; // moving fptr by two
if (sptr == fptr){
// we get the intersection point
break;
}
}
if (sptr == null || fptr == null || fptr.next == null){
// this means the loop not present in the linked list
System.out.print("Loop is not present in the linked list.");
System.out.print("\n");
}
else{
// this means the loop is present in the linked list
System.out.print("Loop is present in the linked list.");
System.out.print("\n");
/* finding the number of nodes in the cycle */
ListNode tempNode = sptr; // starting this node from sptr
int ctr = 0; // to maintain the count of the number of nodes in the loop
while (true){
tempNode = tempNode.next;
ctr++;
if (tempNode == sptr){
break;
}
}
/* finding starting point of the loop */
//Start one pointer from the head of the linked list
ListNode p1 = head;
//Start another pointer from ctr distance ahead of the head of the linked list
ListNode p2 = head;
while (ctr >= 0){
p2 = p2.next;
ctr--;
}
// moving both the pointers together until both of them become equal to
//Find the starting point of the loop
while (p1 != p2){
p1 = p1.next;
p2 = p2.next;
}
//Now both p1 and p2 are pointing to the start node of the loop
// moving sptr to the node preceding the start node in the cycle
while (sptr.next != p1){
sptr = sptr.next;
}
// removing the link between the start node of the loop and the node preceding it in the loop
sptr.next = null;
System.out.print("Loop has been removed from the linked list.");
System.out.print("\n");
}
}
}
Python
# class definition of the ListNode
class ListNode:
def __init__(self, value):
self.val = value
self.next = None
class Globals:
# function to remove loop in linked list using hashing
@staticmethod
def removeLoop(head):
# initializing sptr and fptr
sptr = head
fptr = head
while sptr is not None and fptr is not None and fptr.next is not None:
sptr = sptr.next # moving sptr by one
fptr = fptr.next.next # moving fptr by two
if sptr is fptr:
# we get the intersection point
break
if sptr is None or fptr is None or fptr.next is None:
# this means the loop not present in the linked list
print("Loop is not present in the linked list.", end = '')
print("\n", end = '')
else:
# this means the loop is present in the linked list
print("Loop is present in the linked list.")
""" finding the number of nodes in the cycle """
tempNode = sptr # starting this node from sptr
ctr = 0 # to maintain the count of number of nodes in the loop
while True:
tempNode = tempNode.next
ctr += 1
if tempNode is sptr:
break
""" finding starting point of the loop """
# start one pointer from the head of the linked list
p1 = head
# start another pointer from ctr distance ahead of the head of the linked list
p2 = head
while ctr >= 0:
p2 = p2.next
ctr -= 1
# moving both the pointers together until both of them becomes
# equal to find the starting point of the loop
while p1 is not p2:
p1 = p1.next
p2 = p2.next
# now, both p1 and p2 are pointing to the start node of the loop
# moving sptr to the node preceding the start node in the cycle
while sptr.next is not p1:
sptr = sptr.next
# removing the link between the start node of the loop and the node preceding it in the loop
sptr.next = None
print("Loop has been removed from the linked list.", end = '')
print("\n", end = '')
C++
// class definition of the ListNode
class ListNode{
public:
int val;
ListNode* next;
ListNode(int value){
val=value;
next=NULL;
}
};
// function to remove loop in linked list using floyd-cycle detection
void removeLoop(ListNode* head){
// initializing sptr and fptr
ListNode* sptr = head;
ListNode* fptr = head;
while(sptr!=NULL && fptr!=NULL && fptr->next!=NULL){
sptr = sptr->next; // moving sptr by one
fptr = fptr->next->next; // moving fptr by two
if(sptr == fptr){
// we get the intersection point
break;
}
}
if(sptr==NULL || fptr==NULL || fptr->next==NULL){
// this means the loop is not present in the linked list
cout<<"Loop is not present in the linked list."<<endl;
}
else{
// this means the loop is present in the linked list
cout<<"Loop is present in the linked list."<<endl;
//Finding the number of nodes in the cycle
ListNode* tempNode = sptr; // starting this node from sptr
int ctr = 0; // to maintain the count of the number of nodes in the loop
while(true){
tempNode = tempNode->next;
ctr++;
if(tempNode == sptr){
break;
}
}
//Finding starting point of the loop
//Start one pointer from the head of the linked list
ListNode* p1 = head;
//Start another pointer from ctr distance ahead of the head of the linked list
ListNode* p2 = head;
while(ctr--){
p2 = p2->next;
}
// moving both the pointers together until both of them become equal to find the starting point of the loop
while(p1!=p2){
p1 = p1->next;
p2 = p2->next;
}
//Now both p1 and p2 are pointing to the start node of the loop
// moving sptr to the node preceding the start node in the cycle
while(sptr->next != p1){
sptr = sptr->next;
}
// removing the link between the start node of the loop and the node preceding it in the loop
sptr->next = NULL;
cout<<"Loop has been removed from the linked list."<<endl;
}
}
Complexity Analysis
Time Complexity : The time complexity of the above approach is O(n).
Space Complexity : The space complexity for the above approach is O(1) since we are using only two pointers to detect and remove the loop and no extra space.
Approach 3: Removing Loop Without Counting the Number of Nodes in the Cycle (code in Java, Python, C++)
In this approach, after we know the loop exists in the linked list, we have to remove it. For this, we will take two pointers, p1 and p2. We initialize pointer p1 with the head of the linked list and pointer p2 with the point where the two pointers sptr and fptr become equal.
We will move the pointers p1 and p2 until we reach a state when p1->next becomes equal to p2->next. When the loop terminates, the pointer p2 will point at the node preceding the starting point of the node in the loop.
The representation of how the pointers p1 and p2 move until p1->next becomes equal to p2->next is given below.
To remove the cycle, we can just make p2->next = NULL. This will break the link between the p2 node and the starting point of the loop, removing the cycle.
Proof of Why This Approach Works
The above solution works because the loop’s starting point is at the same distance from the head of the linked list and the point of intersection of sptr and fptr.
This can be proved by using fundamental physics concepts of speed, distance and time.
Given below is the path followed by sprt and fptr.
Let’s define some distances. Let x be the distance between the head and the start node of the loop, y be the distance between the start node of the loop and the intersection point of sptr and fptr and z be the distance between the intersection point of sptr and fptr and the start node of the loop.
These distances are shown in the diagram given below.
Looking at the above two images, we can say that the distance travelled by the pointer sptr = (x + y) and the distance travelled by the node fptr = (x + y + z + y) are equal to (x + 2y + z).
Since the speed of the fptr pointer is twice the speed of the sptr node, let the speeds of sptr and fptr be ‘v’ and ‘2v’, respectively.
In physics, we have a formula – time = distance/speed. So, let’s find the time the two pointers took to reach the intersection point.
Time taken by sptr to reach the intersection point => t1 = (x + y) / v … (equation 1)
Time taken by fptr to reach the intersection point => t2 = (x + 2y + z) / 2v … (equation 2)
Both sptr and fptr reach the intersection point at the same time, so from equations 1 and 2, we can deduce,
t1 = t2
=> (x + y) / v = (x + 2y + z) / 2v
=> 2(x + y) = (x + 2y + z)
=> x = z
Finally, we have proved x (the distance between the head of the linked list and the starting point of the loop) is the same as z (the distance between the intersection point and the starting point of the loop).
Code Implementation
Java
// class definition of the ListNode
public class ListNode{
public int val;
public ListNode next;
public ListNode(int value){
val = value;
next = null;
}
}
public class Globals{
// function to remove loop in linked list using hashing
public static void FloydCycleDetection(ListNode head){
// initializing sptr and fptr
ListNode sptr = head;
ListNode fptr = head;
while (sptr != null && fptr != null && fptr.next != null){
sptr = sptr.next; // moving sptr by one
fptr = fptr.next.next; // moving fptr by two
if (sptr == fptr){
// we get the intersection point
break;
}
}
if (sptr == null || fptr == null || fptr.next == null){
// this means the loop not present in the linked list
System.out.print("Loop is not present in the linked list.");
System.out.print("\n");
}
else{
// this means the loop is present in the linked list
System.out.print("Loop is present in the linked list.");
System.out.print("\n");
/* removing loop */
// initializing pointers p1 and p2
ListNode p1 = head; // initializing to the head of the linked list
ListNode p2 = sptr; // initializing to the intersection point
while (p1.next != p2.next){
p1 = p1.next;
p2 = p2.next;
}
// finally, we have to make p2->next = NULL to remove the loop from the linked list
p2.next = null;
System.out.print("Loop has been removed from the linked list.");
System.out.print("\n");
}
}
}
Python
# class definition of the ListNode
class ListNode:
def __init__(self, value):
self.val = value
self.next = None
class Globals:
# function to remove loop in linked list using hashing
@staticmethod
def FloydCycleDetection(head):
# initializing sptr and fptr
sptr = head
fptr = head
while sptr is not None and fptr is not None and fptr.next is not None:
sptr = sptr.next # moving sptr by one
fptr = fptr.next.next # moving fptr by two
if sptr is fptr:
# we get the intersection point
break
if sptr is None or fptr is None or fptr.next is None:
# this means the loop not present in the linked list
print("Loop is not present in the linked list.", end = '')
print("\n", end = '')
else:
# this means the loop is present in the linked list
print("Loop is present in the linked list.", end = '')
print("\n", end = '')
""" removing loop """
# initializing pointers p1 and p2
p1 = head # initializing to the head of the linked list
p2 = sptr # initializing to the intersection point
while p1.next is not p2.next:
p1 = p1.next
p2 = p2.next
# finally, we have to make p2->next = NULL to remove the loop from the linked list
p2.next = None
print("Loop has been removed from the linked list.", end = '')
print("\n", end = '')
C++
// class definition of the ListNode
class ListNode{
public:
int val;
ListNode* next;
ListNode(int value){
val=value;
next=NULL;
}
};
// function to remove loop in linked list using hashing
void FloydCycleDetection(ListNode* head){
// initializing sptr and fptr
ListNode* sptr = head;
ListNode* fptr = head;
while(sptr!=NULL && fptr!=NULL && fptr->next!=NULL){
sptr = sptr->next; // moving sptr by one
fptr = fptr->next->next; // moving fptr by two
if(sptr == fptr){
// we get the intersection point
break;
}
}
if(sptr==NULL || fptr==NULL || fptr->next==NULL){
// this means the loop not present in the linked list
cout<<"Loop is not present in the linked list."<<endl;
}
else{
// this means the loop is present in the linked list
cout<<"Loop is present in the linked list."<<endl;
/* removing loop */
// initializing pointers p1 and p2
ListNode* p1 = head; // initializing to the head of the linked list
ListNode* p2 = sptr; // initializing to the intersection point
while(p1->next != p2->next){
p1=p1->next;
p2=p2->next;
}
// finally, we have to make p2->next = NULL to remove the loop from the linked list
p2->next = NULL;
cout<<"Loop has been removed from the linked list."<<endl;
}
}
Complexity Analysis
Time Complexity : Since we iterate over each node at most twice (twice in the case of nodes present in the loop), the time complexity of the above approach is O(n).
Space Complexity : The space complexity for the above approach is O(1) since we use only two pointers to detect and remove the loop and no extra space.
Approach 4: Hashing (Hash the Address of the Linked List Nodes)
This approach will use a hashmap to track which node has been visited while traversing the linked list. Below are the steps that explain the algorithms clearly.
- We start from the head node and traverse the linked list.
- If we arrive at a node already visited, this node is the first node of the cycle.
- To remove the loop, we will arrive at a node just preceding the already visited node in the loop and remove the link between these two nodes.
Code Implementation
Java
import java.util.*;
// class definition of the ListNode
public class ListNode{
public int val;
public ListNode next;
public ListNode(int value){
val = value;
next = null;
}
}
public class Globals{
// function to remove loop in linked list using hashing
public static void removeLoopUsingHashing(ListNode head){
HashMap<ListNode,Boolean> visited = new HashMap<ListNode,Boolean>();
ListNode temp = head; // an iterator to iterate the linked list
while (temp != null && temp.next != null && !visited.containsKey(temp.next)){
visited.put(temp, true);
temp = temp.next;
}
if (temp == null || temp.next == null){
// this means that loop is not present in the linked list
System.out.print("Loop is absent in the linked list");
System.out.print("\n");
}
else{
// the node temp->next is the starting of the loop in the linked list
// hence, we can set temp->next = NULL to remove the loop in the linked list
System.out.print("Loop found, loop is starting from the node: ");
System.out.print(temp.val);
System.out.print("\n");
temp.next = null;
System.out.print("Loop as been removed in the linked list");
System.out.print("\n");
}
}
}
Python
# class definition of the ListNode
class ListNode:
def __init__(self, value):
self.val = value
self.next = None
class Globals:
# function to remove loop in linked list using hashing
@staticmethod
def removeLoopUsingHashing(head):
visited = {}
temp = head # an iterator to iterate the linked list
while temp is not None and temp.next is not None and temp.next not in visited.keys():
visited[temp]=True
temp = temp.next
if temp is None or temp.next is None:
# this means that loop is not present in the linked list
print("Loop is absent in the linked list")
else:
# the node temp->next is the starting of the loop in the linked list
# hence, we can set temp->next = NULL to remove loop in linked list
print("Loop found, loop is starting from the node: ", end = '')
print(temp.val, end = '')
print("\n", end = '')
temp.next = None
print("Loop as been removed in the linked list")
C++
// class definition of the ListNode
class ListNode{
public:
int val;
ListNode* next;
ListNode(int value){
val=value;
next=NULL;
}
};
// function to remove loop in linked list using hashing
void removeLoopUsingHashing(ListNode* head){
unordered_map<ListNode*,bool> visited;
ListNode* temp = head; // an iterator to iterate the linked list
while(temp!=NULL && temp->next!=NULL && visited.find(temp->next)==visited.end()){
visited[temp]=true;
temp=temp->next;
}
if(temp==NULL || temp->next==NULL){
// this means that loop is not present in the linked list
cout<<"Loop is absent in the linked list"<<endl;
}
else{
// the node temp->next is the starting of the loop in the linked list
// hence, we can set temp->next = NULL to remove loop in linked list
cout<<"Loop found, loop is starting from the node: "<<temp->val<<endl;
temp->next = NULL;
cout<<"Loop as been removed in the linked list"<<endl;
}
}
Complexity Analysis
Time Complexity : Since we are traversing each node only one time, the time complexity of this approach will be O(n).
Space Complexity : Since we are using a hashmap to store the visited status of each node, the space complexity of the above approach is O(n).
Conclusion
- A linked list is said to have a loop if some node in the list can be reached again by continuously following the next pointer.
- If a linked list has a loop in it, it can be removed in many ways, such as removing the loop by checking nodes one by one, removing the loop without counting the number of nodes in the linked list, removing the loop using hashing and removing loop using Floyd’s cycle detection algorithm.
- The Floyd cycle detection algorithm is the most efficient since it runs in O(n) time and O(1) space.
