In this guide, we will explore techniques for identifying and eliminating loops within a Linked List using various approaches in C++.
Create a function known as checkLoopAndRemove to examine if a provided Linked List contains a loop. Next, eliminate the loop and indicate true if found. If no loop is present, indicate false. A visual representation of a linked list with a loop is shown in the illustration below. The arrangement of the List should be altered to 1->2->3->4->5->NULL by utilizing the checkLoopAndRemove function.
Write a C function to detect a loop in a linked list.
- We must first identify the Loop before attempting to remove it. Loops can be found using the methods discussed in the section above. All we have to do to end the Loop is obtain a pointer to the Loop's final node. Consider the node in the diagram above with the value 5. Once we know which node is the final, we may make the next node in this chain NULL to end the Loop.
- We may quickly apply the hashing or visited node approaches to obtain the pointer to the last node. The concept is straightforward: the final node is the first node whose next has already been visited (or hashed).
- The Floyd Cycle Detection technique can be used to find and get rid of the Loop as well. The slow and fascpp tutorialers in Floyd's algorithm come together at a loop node. This loop node can be used to get rid of the cycle. When Floyd's technique detects loops, two distinct approaches exist to break the Loop.
Method 1: (Check each one separately)
Floyd's Cycle detection algorithm terminates once the fast and slow pointers converge at a shared position, which is known to be a node within the loop (2, 3, 4, or 5 as illustrated). Store this location in a pointer variable, such as ptr2. Subsequently, commence from the Linked List's head and verify the reachability of each node from ptr2 by inspecting them individually. As a node becomes reachable, we can retrieve the pointer to its preceding node, signifying that this particular node marks the start of the loop.
Output:
Linked List after removing Loop
50 20 15 4 10
Method 2: (Better Solution)
- This technique also requires Floyd's Cycle detection
- Get the pointer to a loop node by utilizing Floyd's Cycle detection technique to find a loop.
- Count how many nodes are in the Loop. Let k be the count.
- One pointer should be fixed to the head and the other to a kth node from the head.
- The pointers will collide at the Loop's starting node if we move them both at the same speed.
- Obtain a pointer to the Loop's final node and make the next one NULL.
Program:
Let's consider an illustration to demonstrate the process of identifying and eliminating a loop in a linked list using C++.
#include <bits/stdc++.h>
using namespace std;
/* Link list node */
struct Node {
int data;
struct Node* next;
};
/* Function to remove Loop. */
void removeLoop(struct Node*, struct Node*);
/* This Function detects and removes Loop in the
List
If Loop was there in the List, then it returns 1,
otherwise returns 0 */
int detectAndRemoveLoop(struct Node* list)
{
struct Node *slow_p = list, *fast_p = list;
// Iterate and find if Loop exists or not
while (slow_p && fast_p && fast_p->next) {
slow_p = slow_p->next;
fast_p = fast_p->next->next;
/* If slow_p and fast_p meet at some point, then there is a loop */
if (slow_p == fast_p) {
removeLoop(slow_p, list);
/* Return 1 to indicate that Loop is found */
return 1;
}
}
/* Return 0 to indicate that 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* ptr1 = loop_node;
struct Node* ptr2 = loop_node;
// Count the number of nodes in the Loop
unsigned int k = 1, i;
while (ptr1->next != ptr2) {
ptr1 = ptr1->next;
k++;
}
// Fix one pointer to head
ptr1 = head;
// And the other pointer to k nodes after head
ptr2 = head;
for (i = 0; i < k; i++)
ptr2 = ptr2->next;
/* Move both pointers at the same pace,
they will meet at Loop starting node */
while (ptr2 != ptr1) {
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}
// Get a pointer to the last node
while (ptr2->next != ptr1)
ptr2 = ptr2->next;
/* Set the next node of the Loop ending node
to fix the Loop */
ptr2->next = NULL;
}
/* Function to print linked List */
void printList(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(35);
head->next = newNode(10);
head->next->next = newNode(12);
head->next->next->next = newNode(54);
head->next->next->next->next = newNode(5);
/* Create a loop for testing */
head->next->next->next->next->next = head->next->next;
detectAndRemoveLoop(head);
cout << "Linked List after removing loop \n";
printList(head);
return 0;
}
Output:
Complexity Analysis:
The time complexity is O(N), where N represents the total count of nodes within the tree.
Auxiliary Space: O(1)
Method 3: (Without Counting Nodes in Loop)
The count of nodes within the Loop doesn't require manual calculation. Once the Loop is recognized, advancing the fast and slow pointers simultaneously until they do not intersect, they will converge at the Loop's starting point.
How does this work?
Let the Floyd's Cycle detection algorithm reach a point where the slow and fast pointers intersect. The moment when the algorithm detects the cycle is illustrated in the diagram provided.
We can conclude from the above diagram.
Distance traveled by fascpp tutorialer = 2 * (Distance traveled by slow pointer)
(m + n*x + k) = 2*(m + n*y + k)
Note that before meeting the point shown above, fast was moving at twice the speed.
x --> Number of complete cyclic rounds made by
fascpp tutorialer before they meet the first time
y --> Number of complete cyclic rounds made by
slow pointer before they meet the first time
From the above equation, we can conclude below
m + k = (x-2y)*n
Which means m+k is a multiple of n.
Thus we can write m + k = i*n or m = i*n - k.
Hence, the distance moved by the slow pointer: m, is equal to the distance moved by the fascpp tutorialer:
i*n - k or (i-1)*n + n - k (cover the loop completely i-1 times and start from n-k).
As a consequence, when both pointers resume moving simultaneously, one pointer (referred to as slow) will commence from the head node of the linked list, while the other (referred to as fast) will begin from the meeting point. The latter pointer would also have traveled m steps since they are now moving at an equal pace. As the slow pointer reaches the start of the loop after covering m steps, they will intersect at the initial point because the fast pointer begins from k, and the sum of m and k is a multiple of n.
Program:
// C++ program to detect and remove Loop
#include <bits/stdc++.h>
using namespace std;
struct Node {
int key;
struct Node* next;
};
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->next = NULL;
return temp;
}
// A utility function to print a linked list
void printList(Node* head)
{
while (head != NULL) {
cout << head->key << " ";
head = head->next;
}
cout << endl;
}
//Function to detect and remove Loop in a linked list that
// may contain Loop
void detectAndRemoveLoop(Node* head)
{
// If the List is empty or has only one node without Loop
if (head == NULL || head->next == NULL)
return;
Node *slow = head, *fast = head;
// Move slow and fast 1 and 2 steps ahead, respectively.
slow = slow->next;
fast = fast->next->next;
// Search for Loop using slow and fascpp tutorialers
while (fast && fast->next) {
if (slow == fast)
break;
slow = slow->next;
fast = fast->next->next;
}
/* If loop exists */
if (slow == fast) {
slow = head;
//This check is needed when slow and fast both meet
// at the head of the LL eg: 1->2->3->4->5 and then
// 5->next = 1, i.e the head of the LL
if (slow == fast)
while (fast->next != slow)
fast = fast->next;
else {
while (slow->next != fast->next) {
slow = slow->next;
fast = fast->next;
}
}
/* since fast->next is the looping point */
fast->next = NULL; /* remove loop */
}
}
/* Driver program to test above Function*/
int main()
{
Node* head = newNode(35);
head->next = head;
head->next = newNode(10);
head->next->next = newNode(54);
head->next->next->next = newNode(5);
head->next->next->next->next = newNode(10);
/* Create a loop for testing */
head->next->next->next->next->next = head;
detectAndRemoveLoop(head);
printf("Linked List after removing loop \n");
printList(head);
return 0;
}
Output:
Complexity Analysis:
Time Complexity: O(N), where N represents the total count of nodes within the tree.
Auxiliary Space: O(1)
Method 4: Hashing (Hash the linked list nodes' addresses)
We can verify the presence of an element in the map by hashing the addresses of the linked list nodes within an unordered map. It is essential to assign the last node's pointer to NULL as it indicates the end of the list and helps detect cycles in the linked list structure.
Program:
// C++ program to detect and remove Loop
#include <bits/stdc++.h>
using namespace std;
struct Node {
int key;
struct Node* next;
};
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->next = NULL;
return temp;
}
// A utility function to print a linked list
void printList(Node* head)
{
while (head != NULL) {
cout << head->key << " ";
head = head->next;
}
cout << endl;
}
//Function to detect and remove the loop
// in a linked list that may contain Loop
void hashAndRemove(Node* head)
{
// hash map to hash addresses of the linked list nodes
unordered_map<Node*, int> node_map;
// pointer to the last node
Node* last = NULL;
while (head != NULL) {
//If node not present in the map, insert it in the map
if (node_map.find(head) == node_map.end()) {
node_map[head]++;
last = head;
head = head->next;
}
//If present, it is a cycle; make the last node's nexcpp tutorialer NULL
else {
last->next = NULL;
break;
}
}
}
/* Driver program to test above Function*/
int main()
{
Node* head = newNode(35);
head->next = head;
head->next = newNode(10);
head->next->next = newNode(54);
head->next->next->next = newNode(5);
head->next->next->next->next = newNode(10);
/* Create a loop for testing */
head->next->next->next->next->next = head->next->next;
// printList(head);
hashAndRemove(head);
printf("Linked List after removing loop \n");
printList(head);
return 0;
}
Output:
Complexity Analysis:
The time complexity is O(N), where N represents the total count of nodes within the tree structure.
Additional Memory Usage: O(N), where N represents the total count of nodes in the tree (attributable to the implementation of hashing).
