Linked List Detect Cycle | JavaScript

Difficulty Level: Medium
Asked In: Amazon, Microsoft, SAP Labs

Let’s understand the problem

We are given an head node of the linked list and our task is to find if there is any loop in the linked list like the image given below.

Algorithm:

Let’s assume two friends starts running around a circular path from same point and with same speed they will not be able to cross each other at any time. Now let’s assume both of the friends are running with the different after some running for some time friend who are was running fast will find that the slow friend is in front of him so this will confirm that they are running in the loop.

We will be using two pointer approach over here. One pointer will be called fast and other will be slow.

fast will move 2 node at a time and slow node will move 1 node forward at a time if at any given time the fast == slow there is loop confirmed.

class Node{
    constructor(value){
        this.value = value;
        this.next = null
    }
}
let list = new Node(1);
list.next = new Node(2);
list.next.next = new Node(3)
list.next.next.next = new Node(4)
list.next.next.next.next = new Node(5)
list.next.next.next.next.next = list.next.next //Creating loop
detectLoop = (node)=>{
    fast = node;
    slow = node;
    while(fast && fast.next){
        fast = fast.next.next;
        slow = slow.next;
        if(fast == slow){
            return true
        }
    }
    return false;
}
console.log(detectLoop(list)) // true

Hope you liked the post and find it useful.
Read More at: https://www.geeksforgeeks.org/detect-loop-in-a-linked-list.
If you have any ideas/queries/doubts/feedback, please comment below or write us at manangupta657@gmail.com. Enjoy learning, Enjoy coding, Enjoy algorithms!