Hashing Approach

Floyd’s Cycle Detection Algorithm (also known as the “Tortoise and Hare” approach)

It uses a set to record visited entries when it is travelling along. For instance, if there exists a node that has already been placed on the set while travelling through the list means that there is a loop. To remove the loop after detecting it, we need to initialize the last node’s next pointer as null.

Algorithm:

Keep a record of the visited nodes using a set.
Adding each node to the set when traversing the list.
The presence of a node in the set indicates that there is a loop.
Make sure that the last node’s next pointer is `null` to eliminate the loop.

Example: To demonstrate removing loop in a linked list using the hashing approach.

JavaScript

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 Hashing Approach
function removeLoopHashing(head) {
    const visitedNodes = new Set();
    // Set to keep track of visited nodes
    let current = head;
    let prev = null;

    // Traverse the list
    while (current) {
        // If current node is already 
        // visited, loop detected
        if (visitedNodes.has(current)) {
            prev.next = null;
            // Remove loop by setting 
            // the previous node's next to null
            console.log('Loop removed');
            return;
        }
        visitedNodes.add(current);
        prev = current;
        current = current.next;
    }
}

// Removing loop 
// using Hashing Approach
removeLoopHashing(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

Tags:

#JavaScript-Program #JavaScript #Web Technologies

Floyd’s Cycle Detection Algorithm (also known as the “Tortoise and Hare” approach)

Hashing Approach

Algorithm:

JavaScript Program to Remove Loop in a Linked List

Similar Reads

Contact Us