Problem
Given the head pointer (head) of a linked list, check whether there’s a loop in the linked list. Return true if a loop is present and false otherwise.
Detect Loop
Naive Approach
We could maintain a hashmap (hmap) storing the node address of each node as we traverse the linked list. If we reach a node which was already present in the hmap return true and return false if we reach NULL.
Pseudocode
DetectLoop (head):
node = head
while (node != NULL):
if (map.find[node]):
return true
map[node] = 1
node = node->next
return false
Optimised Approach: Floyd’s Cycle-Finding (tortoise and hare) Algorithm
The idea is to have two head pointers to the given linked list and move them at different speeds. Move one pointer (ptr1) forward by one node and second pointer (ptr2) by two nodes. Now two things could happen:
- If the linked list has a loop, the two pointers will definitely meet somewhere inside the loop. This is because they are moving at different speeds, in a same circular path.
- Else either of the two pointers will become
null.
Time Complexity: O(N), N is the length of the linked list
Code Implementation
bool hasLoop (Node *head) {
if (head == NULL || head->next == NULL) {
return false;
}
Node *ptr1 = head->next, *ptr2 = head->next->next;
while (ptr1 != NULL && ptr2 != NULL && ptr2->next != NULL) {
if (ptr1 == ptr2) {
return true;
}
ptr1 = ptr1->next;
ptr2 = ptr2->next->next;
}
return false;
}
Remove Loop
In order to remove the loop, we need the count of the number of nodes in the loop, let it be k.
Pseudocode
1. Let ptr1 = head, ptr2 = kth node from the head 2. Move ptr1 and ptr2 by 1 node each 3. ptr1 and ptr2 will meet at the starting node of the loop 4. Set the next of the meeting node to NULL
Code Implementation
void removeLoop (Node *head, Node *ptr) {
Node *ptr1 = head, *ptr2 = head;
int k = findLoopLength (ptr);
for (int i=0; i<k && ptr2 != NULL; i++) {
ptr2 = ptr2->next;
}
while (ptr1 != ptr2) {
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}
while (ptr2->next != ptr1) {
ptr2 = ptr2->next;
}
ptr2->next = NULL;
}
bool detectAndRemoveLoop (Node *head) {
if (head == NULL || head->next == NULL) {
return false;
}
Node *ptr1 = head->next, *ptr2 = head->next->next;
while (ptr1 != NULL && ptr2 != NULL && ptr2->next != NULL) {
if (ptr1 == ptr2) {
removeLoop(head, ptr1);
return true;
}
ptr1 = ptr1->next;
ptr2 = ptr2->next->next;
}
return false;
}
How does Floyd’s Cycle-Finding Algorithm work? (Proof)
Here’s the explanation for why the two pointers (ptr1 & ptr2) meet at the starting node of the loop:
Case 1: (c > k)
Now, to detect the starting point of loop, let’s assume ptr1 and ptr2 meet at a point x:
Initially, ptr1 = 0, ptr2 = k ptr2 after c-k + k (1 round in the loop) = c steps, would be at the starting point of the loop. And ptr1 after c steps would also be at the starting point of the loop ie. x. Hence both ptr1 and ptr2 would travel c distance to meet at the starting point of the loop.
Case 2: (c < k)
Initially, ptr1 = 0, ptr2 = k ptr2 after k-t steps would be at the starting point of the loop. Since, k - t = k - (k-c) = c steps And ptr1 after c steps would also be at starting point of the loop ie. x. Hence both ptr1 and ptr2 would travel c distance to meet at the starting point of the loop.
Here’s the complete code:
//
// main.cpp
// Detect and Remove Loop (Linked List)
//
// Created by Himanshu on 11/07/22.
//
#include <iostream>
using namespace std;
struct node {
int info = 0;
struct node *next;
};
typedef struct node Node;
node* newNode(int data) {
node* Node = new node();
Node->info = data;
Node->next = NULL;
return(Node);
}
void printLinkedList (Node* head) {
Node *x = head;
while (x != NULL) {
cout<<(x->info)<<" ";
x = x->next;
}
cout<<endl;
}
Node* insertNode (Node *head, Node* x) {
Node *node = head;
while (node->next != NULL) {
node = node->next;
}
x->next = NULL;
node->next = x;
return head;
}
int findLoopLength (Node *head) {
int len = 1;
Node *node = head;
while (node != NULL && node->next != head) {
len++;
node = node->next;
}
return len;
}
void removeLoop (Node *head, Node *ptr) {
Node *ptr1 = head, *ptr2 = head;
int k = findLoopLength (ptr);
for (int i=0; i<k && ptr2 != NULL; i++) {
ptr2 = ptr2->next;
}
while (ptr1 != ptr2) {
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}
while (ptr2->next != ptr1) {
ptr2 = ptr2->next;
}
ptr2->next = NULL;
}
bool detectAndRemoveLoop (Node *head) {
if (head == NULL || head->next == NULL) {
return false;
}
Node *ptr1 = head->next, *ptr2 = head->next->next;
while (ptr1 != NULL && ptr2 != NULL && ptr2->next != NULL) {
if (ptr1 == ptr2) {
removeLoop(head, ptr1);
return true;
}
ptr1 = ptr1->next;
ptr2 = ptr2->next->next;
}
return false;
}
int main() {
Node *head1 = newNode(1);
head1 = insertNode (head1, newNode(2));
Node* loopHead = newNode(3);
head1 = insertNode (head1, loopHead);
head1 = insertNode (head1, newNode(4));
Node* loopTail = newNode(5);
head1 = insertNode (head1, loopTail);
loopTail->next = loopHead;
Node *head2 = newNode(6);
head2 = insertNode (head2, newNode(7));
head2 = insertNode (head2, newNode(8));
if (detectAndRemoveLoop(head1)) {
cout<<"Linked List 1 has a loop:"<<endl;
printLinkedList(head1);
} else {
cout<<"Linked List 1 does not have a loop:"<<endl;
printLinkedList(head1);
}
if (detectAndRemoveLoop(head2)) {
cout<<"Linked List 2 has a loop:"<<endl;
printLinkedList(head2);
} else {
cout<<"Linked List 2 does not have a loop:"<<endl;
printLinkedList(head2);
}
return 0;
}
Output
Linked List 1 has a loop: 1 2 3 4 5 Linked List 2 does not have a loop: 6 7 8