Learn how to find or detect loop in linked list.
For example.
Input: 4 -> 10 -> 12 -> 33 -> 3 3 -> 7 -> 11 -> 22 -> 7 Output: false true
As the element of the first input does not points to any existing element of the list which specifies that it does not have any loop.
But the element of the second list is pointing to the existing element present in the list, so it has a loop.
We have to create an algorithm which should be able to detect this loop in the linked list.
For this we will check out three different approaches.
Using Set to detect loop in linked list.
We will iterate all the elements of the list and store them in a SET. Before storing the element we will verify if it is already present or not. If it is present then the list has a loop.
const detectLoop = (node) => {
//Set to store elements
let s = new Set();
while(node){
//Check if store has the element
//Then return true
if(s.has(node.element)){
return true;
}
//Add the element to the set
s.add(node.element);
node = node.next;
}
return false;
}
Input: let node = new LinkedList(); node.append(20); node.append(4); node.append(15); node.append(10); let head = node.getHead(); //Create a loop so that we can detect it head.next.next.next.next = head; let hasLoop = detectLoop(node.getHead()); console.log(hasLoop); Output: true
Time complexity: O(n).
Space complexity: O(n).
Using Floyd’s Cycle-Finding Algorithm
Floyd’s Cycle-Finding also know as Floyd’s Tortoise and Hare algorithm is used to find loop in the linked list.
It uses a simple approach of using to pointers to detect the loop. The first pointer run as usual to the next element (like Tortoise) by one, but the second pointer moves faster to the next.next element (like hare) by two.
If these pointers at any given time meet at the same node then there is a loop. If pointers do not meet then linked list doesn’t have a loop.
const detectLoop = (node) => {
//Use two pointers
let tortoise = node, hare = node;
while (hare && hare.next) {
//Move slow by one
tortoise = tortoise.next;
//Move fast by two
hare = hare.next.next;
//If they meet then there is a loop
if (tortoise === hare) {
return true;
}
}
return false;
}
Input: let node = new LinkedList(); node.append(20); node.append(4); node.append(15); node.append(10); let head = node.getHead(); //Create a loop so that we can detect it head.next.next.next.next = head; let hasLoop = detectLoop(node.getHead()); console.log(hasLoop); Output: true
Time complexity: O(n).
Space complexity: O(1).
Marking visited nodes without modifying the linked list data structure
In this approach we will use a temporary node as marker. The next pointer of each node that is traversed is made to point this temporary node.
By doing this we are using the temporary node as a flag to indicate whether the node has been traversed or not.
Every node is checked to see if it is pointing to the temp node or not. If we come across a node that is pointing to the null then loop does not exists. Else it exists.
//Temp node
let Node = function(elm) {
this.element = elm;
this.next = null;
}
const detectLoop = (node) => {
let temp = new Node();
while(node){
// This condition is for the case
// when there is no loop
if (node.next == null) {
return false;
}
// Check if next is already
// pointing to temp
if (node.next && temp && node.next.element == temp.element) {
return true;
}
// Store the pointer to the next node
// in order to get to it in the next step
let nex = node.next;
// Make next point to temp
node.next = temp;
// Get to the next node in the list
node = nex;
}
}
Input: let node = new LinkedList(); node.append(20); node.append(4); node.append(15); node.append(10); let head = node.getHead(); //Create a loop so that we can detect it head.next.next.next.next = head; let hasLoop = detectLoop(node.getHead()); console.log(hasLoop); Output: true
Time complexity: O(n).
Space complexity: O(1).