Let's start by understanding the problem statement of detecting a loop in a linked list.
Given a linked list, you have to detect if the linked lists form a loop.
Hint:
A loop in a linked list is a structure where the next node of the terminal node in a linked list is connected to one of the already existing nodes in the linked list, as shown in the diagram below:-
Here the tail node with data 10 is linked to a node of the linked list with data 45 creating a loop. One way to solve this problem is to make use of the hash set and store the data nodes and check whether the data node already inserted in the linked list exists or not, if not then there is no loop else the linked list has a loop.
Quick Think:
For checking a loop in the given linked list the condition to be checked every time when we move to the next node in the linked list is the current node should not be NULL and if the end of the list is traversed without finding the loop then there is no loop in the given linked list else the linked list contains a loop.
Algorithm:
A function is defined with the argument as the head of the linked list and the following steps are followed to check for the loop in the given linked list:-
Step1: The reference of the head node of the linked list is stored in a temporary node and defined as an unordered set to store the data nodes.
Step2: The node is checked for not being NULL if the temporary node is NULL go to step 4 else go to step 3.
Step3: Check for the data of the node whether it is stored in the unordered set or not is ‘Yes’ then return ‘True’ else insert the current node into the unordered set and traverse to the next node in the linked list.
Step4: If the terminal of the linked list is reached, then return 'False'.
Implementation Of The Above Algorithm:
Now let's see the implementation of the above algorithm.
#include <bits/stdc++.h>
using namespace std;
struct node
{
int data;
struct node * next;
};
/*Function to create the linked list. */
void push(struct node **head_ref, int data)
{
struct node * node;
node = (struct node *) malloc(sizeof(struct node));
node->data = data;
node->next = (*head_ref);
(*head_ref) = node;
}
/*Function to check the loop in the linked list. */
bool findloop(struct node **head_ref)
{
struct node *temp = (*head_ref);
unordered_set<node*> set;
while (temp != NULL)
{
/*If data node is found in the unordered set then there is a loop in the linked list. */
if (set.find(temp) != set.end())
return true;
set.insert(temp);
temp = temp->next;
}
/*Else there is no loop in the linked list. */
return false;
}
/*Driver program to check the above algorithm*/
int main()
{
/*Start with the empty list */
struct node *head = NULL;
push(&head, 10);
push(&head, 20);
push(&head, 67);
push(&head, 45);
push(&head, 80);
push(&head, 9);
/*Create a loop for testing the above algorithm.*/
head->next->next->next->next->next = head->next;
if (findloop(&head))
cout << "Loop found";
else
cout << "No Loop found";
return 0;
}
The running time complexity of the above algorithm is: O(n).
The output of the above algorithm is: Loop found.
Explanation Of The Above Algorithm:
Let us take an example of the above-linked list as mentioned in the above algorithm, as shown in the diagram below.
- Now after we have defined an unordered set our pointer is pointing toward the head node of the linked list and since the current data node is not present in the unordered set so the data node 9 is pushed into the unordered set as shown in the diagram below.
- Now we move on to the next node and now our pointer is pointing towards the next node to that of the head node i.e., the node with data 80 since this node data is also not present in the unordered set so, we again push the current data node to the unordered set as shown in the diagram below.
- Now moving on to the next node in the linked list which is the node with data
45 and push this node to the unordered set as this data is also not present in the unordered set before as shown in the diagram below.
- Similarly, moving on to the next node in the linked list which is the node with data
67 and push this node to the unordered set as this data is also not present in the unordered set before as shown in the diagram below.
- Now, move on to the next node in the linked list which is the node with data 20, and push this node to the unordered set as this data is also not present in the unordered set before as shown in the diagram below.
- Now our pointer points to the last node of the linked list and the terminal node with data
10 is pushed into the unordered set as shown in the diagram below.
- Now when we move on to the next node of our terminal node o the linked list given we see that the node with data 45 already exists in the unordered set and hence, according to our algorithm ‘
True’ is returned and hence, “Loop found” gets printed.
