Marking Approach
In this method, flagging nodes as visited indicates that they have been visited before. If some entry is already flagged as being visited before, it means there exists a loop. After identifying such scenarios represented by detected loops, then their removal will follow by setting next pointer’s last node inside given loop into nulls only.
Algorithm:
- Flagging each node after iterating through with `visited`.
- If discovered as being visited, denotes that there exists a loop
- However, reset all links between nodes prior to this beginning of such circularity so as not produce cycles
Example: To demonstrate removing the loop in a linked list using the marking approach.
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
// Function to print the linked
// list up to 20 nodes for simplicity
function printList(head) {
let current = head;
let count = 0;
while (current && count < 20)
{
console.log(current.value);
current = current.next;
count++;
}
}
// Function to create a
// loop in the linked list
function createLoop(head, loopIndex)
{
let current = head;
let loopNode = null;
let index = 0;
while (current.next) {
if (index === loopIndex)
{
loopNode = current;
}
current = current.next;
index++;
}
current.next = loopNode;
// Create loop by linking the
// last node to the loopNode
}
// Example usage
const head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(5);
// Create a loop at
// index 2 (Node with value 3)
createLoop(head, 2);
console.log("Before removing loop:");
printList(head);
// Function to remove
// loop using Marking Approach
function removeLoopMarking(head)
{
let current = head;
let prev = null;
// Traverse the list
while (current) {
// If current node is
// visited, loop detected
if (current.visited) {
prev.next = null;
// Remove loop by setting the
// previous node's next to null
console.log('Loop removed');
return;
}
current.visited = true;
// Mark current node as visited
prev = current;
current = current.next;
}
}
// Removing loop
// using Marking Approach
removeLoopMarking(head);
console.log("\nAfter removing loop:");
printList(head);
Output
Before removing loop: 1 2 3 4 5 3 4 5 3 4 5 3 4 5 3 4 5 3 4 5 Loop removed After removing loop: 1 2 3 4 5
Time Complexity: O(n)
Space Complexity: O(n)
JavaScript Program to Remove Loop in a Linked List
A linked list is a collection of nodes that contain both a data element and a reference (or pointer) to the next node in the collection. A common concern with linked lists is having loops and cycles. When one of the nodes in the linked list points towards any of its previous nodes leading to an infinite cycle. While traversing the list, this can cause problems due to the loop.
There are several approaches to removing the loop in a linked list using JavaScript which are as follows:
Table of Content
- Hashing Approach
- Floyd’s Cycle Detection Algorithm
- Marking Approach