JavaScript program to find the length of a loop in a linked list

In this program we will get a linked list that may contain loops and we have to find out if the loop exists and then what is the size of the loop. Let us use a very famous method to find the length of a loop with the help of code and discuss its time and space complexity.

Problem Introduction

In this question, as we saw above, we are given a linked list which may or may not contain a loop, if the loop exists, we have to find the length of the loop, otherwise we have to return zero, because There is no loop. We will use the Floyd loop method to find loops and then check their size. For example, if we are given a linked list -

List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8

There is a cycle from the node containing 8 to the node containing 4, which means 8 is connected with 4, forming a cycle of length 5, we have to detect it.

method

In this question, we will use the Floyd loop method to detect loops, and then we will use the concept of length lookup to find the length of the loop. Let's look at the basic steps of the problem first, and then we'll move on to the Freudian method and the length method.

• First, we will create a class to provide the basic structure of the linked list nodes and define a constructor in it to initialize the node values.

• Then we create a function to push elements into the given linked list.

• We create a linked list using the above method and then link the last node to another node to form a loop within it.

Freud’s Algorithm

In this algorithm, we traverse the linked list. Once we enter the linked list, we cannot exit from any node. This means that if we have two pointers in the circular part of the linked list and one pointer moves one node at a time and the other moves two nodes at a time, they will meet at some point.

• After implementing the algorithm, we will call the function and check if the loop exists

• If there is a loop, we will call the anther function to find the length of the loop.

• On the other hand, we will go back and print that there is no loop.

Example

In the following example, we define a linked list and add 8 nodes to it. We form a loop in the linked list by connecting node 8 to node 4. Therefore, it forms a loop of five nodes.

// class to provide the structure to the linked list node
class Node{
   constructor(data) {
      this.value = data
      this.next = null;
   }
}
// function to add values in a linked list
function push(data, head) {
   var new_node = new Node(data);
   if(head == null) {
      head = new_node;
      return head;
   }
   var temp = head
   while(temp.next != null) {
      temp = temp.next;
   }
   temp.next = new_node;
   return head;
}
// function to find the length in the loop 
function length(loop_node) {
   var count = 1;
   var temp = loop_node;
   while(temp.next != loop_node) {
      count++;
      temp = temp.next;
   }
   console.log("The length of the loop in the given linked list is: " + count);
}
// function to find the cycle in the given list 
// if the cycle is found then call the length function 
function find_node(head) {
   var slow_ptr = head;
   var fast_ptr = head;
   while(slow_ptr != null && fast_ptr != null && fast_ptr.next != null) {
      slow_ptr = slow_ptr.next;
      fast_ptr = fast_ptr.next.next;
      if(slow_ptr == fast_ptr) {
         length(slow_ptr);
         return;
      }
   }
   console.log("There is no loop present in the given linked list");
}

var head = null;

head = push(1,head)
head = push(2,head)
head = push(3,head)
head = push(4,head)
head = push(5,head)
head = push(6,head)
head = push(7,head)
head = push(8,head)

// making loop in a linked list by connecting 8 to four 
var temp = head;
while(temp.value != 4){
   temp = temp.next;
}
var temp2 = head;
while(temp2.next != null){
   temp2 = temp2.next
}
temp2.next = temp
// finding the length of the loop 
find_node(head)

Time and space complexity

In the above code, we only traverse the complete linked list once, and the loop part is traversed up to three times, which makes the time complexity linear. So the time complexity of the above code is linear, i.e. O(N), where N is the size of the linked list.

Since we are not using any extra space, the time complexity of the program is O(1).

in conclusion

In this tutorial, we have learned how to find the length of a loop present in a linked list by implementing the concept in JavaScript language. We used Floyd's loop finding algorithm to find a loop in a given linked list, and then we used a while loop to iterate through the loop and find its length. The time complexity of the above code is O(N) and the space complexity is O(1).

The above is the detailed content of JavaScript program to find the length of a loop in a linked list. For more information, please follow other related articles on the PHP Chinese website!