Linked List: Has Loop

Topic

Implement a member function called hasLoop() that checks if the linked list has a loop or not.

Output:

• Return true if the linked list has a loop.
• Return false if the linked list does not have a loop.

Constraints:

• You are not allowed to use any additional data structures (such as arrays) or modify the existing data structure.
• You can only traverse the linked list once.

Example 1:

Suppose you have a LinkedList object, list, with the following values:
1 -> 2 -> 3 -> 4 -> 5, and no loop

After calling the hasLoop() function:

let result = list.hasLoop();

The result should be false.

Example 2:

Now suppose you have a LinkedList object, list, with the following values:
1 -> 2 -> 3 -> 4 -> 5 -> 6, and a loop exists between nodes 6 and 3

After calling the hasLoop() function:

let result = list.hasLoop();

The result should be true.

Pseudo Code:

1. Initialize slow pointer to the head of the list

2. Initialize fast pointer to the head of the list

3. Loop while fast pointer is not null and fast pointer’s next node is not null

a. Move slow pointer one step ahead in the list

b. Move fast pointer two steps ahead in the list

c. Check if slow pointer and fast pointer are the same

• If yes, return true (loop found)
• Return false (loop not found)

Solution Explaination

hasLoop() {
   let slow = this.head;
   let fast = this.head;

   while (fast !== null && fast.next !== null) {
       slow = slow.next;
       fast = fast.next.next;
       
       if (slow === fast) {
          return true;
        }
   }
   
   return false;
}

The hasLoop() function is used to detect if a linked list contains a loop (cycle) or not.

It also utilizes the "tortoise and hare" algorithm.

Here's a step-by-step explanation of the logic:

1. Initialize two pointers, slow and fast, both pointing to the head of the linked list.
2. Traverse the linked list using a while loop. The loop continues as long as fast is not null (i.e., it has not reached the end of the list), and fast.next is also not null (i.e., there is at least one more node after the current fast node).
3. Inside the loop, move the slow pointer one step forward (i.e., slow = slow.next) and the fast pointer two steps forward (i.e., fast = fast.next.next).
4. Check if the slow and fast pointers have become equal. If they have, it means there is a loop in the linked list, and the function returns true.
5. If the loop terminates without the slow and fast pointers becoming equal, it means the linked list has no loop, and the function returns false.

The “tortoise and hare” algorithm works by having two pointers move at different speeds through the linked list. If there is a loop, the faster pointer (the hare) will eventually catch up to the slower pointer (the tortoise) inside the loop. If there is no loop, the faster pointer will reach the end of the list.

Code with inline comments:

hasLoop() {
    // Initialize slow and fast pointers at head
    let slow = this.head;
    let fast = this.head;
    // Iterate through the list
    while (fast !== null && fast.next !== null) {
        // Move slow pointer one step
        slow = slow.next;
        // Move fast pointer two steps
        fast = fast.next.next;
        // If slow and fast pointers meet, loop exists
        if (slow === fast) {
            return true;
        }
    }
    // If no loop is found, return false
    return false;
}

Full Code

class Node {
    constructor(value){
        this.value = value;
        this.next = null;
    }
}
 
class LinkedList {
    constructor(value) {
        const newNode = new Node(value);
        this.head = newNode;
        this.tail = newNode;
        this.length = 1;
    }

    printList() {
        let temp = this.head;
        while (temp !== null) {
            console.log(temp.value);
            temp = temp.next;
        }
    }

    getHead() {
        if (this.head === null) {
            console.log("Head: null");
        } else {
            console.log("Head: " + this.head.value);
        }
    }

    getTail() {
        if (this.tail === null) {
            console.log("Tail: null");
        } else {
            console.log("Tail: " + this.tail.value);
        }
    }

    getLength() {
        console.log("Length: " + this.length);
    }

    makeEmpty() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
 
    push(value) {
        const newNode = new Node(value);
        if (!this.head) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
    }
    
    hasLoop() {
        let slow = this.head;
        let fast = this.head;
        while (fast !== null && fast.next !== null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow === fast) {
                return true;
            }
        }
        return false;
    }
}



let myLinkedList = new LinkedList(1);
myLinkedList.push(2);
myLinkedList.push(3);
myLinkedList.push(4);
myLinkedList.push(5);

console.log("Original list:");
myLinkedList.printList();

const hasLoopResult = myLinkedList.hasLoop();
console.log(`\nHas loop? ${hasLoopResult}`);

// Create a loop for testing purposes
myLinkedList.tail.next = myLinkedList.head.next; // Create a loop by linking tail to the second node

const hasLoopResultAfterLoop = myLinkedList.hasLoop();
console.log(`\nHas loop after creating a loop? ${hasLoopResultAfterLoop}`);


/*
    EXPECTED OUTPUT:
    ----------------
    Original list:
    1
    2
    3
    4
    5
    Has loop? false
    Has loop after creating a loop? true
*/