JavaScript 用于在链表中查找循环的长度

在这个程序中，我们将获得一个可能包含循环的链表，我们需要找出循环是否存在，如果存在，则循环的大小是多少。让我们通过一个代码来找到循环的长度并讨论其时间和空间复杂度。

问题介绍

在这个问题中，我们已经看到，我们将获得一个可能包含循环的链表，我们必须找出循环的长度，如果不存在循环，则返回零，因为没有循环存在。我们将使用弗洛伊德循环方法来找到循环，然后检查其大小。例如，如果我们给出一个链表如下 –

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

并且从包含8的节点到包含4的节点有一个循环，这意味着8与4相连，形成了长度为5的循环，我们必须检测它。

方法

在这个问题中，我们将使用弗洛伊德循环方法来检测循环，然后我们将使用长度查找的概念来找到循环的长度。让我们先看一下问题的基本步骤，然后我们将转到弗洛伊德的方法和长度的方法。

首先，我们将创建一个类来提供链表节点的基本结构，并在其中定义构造函数来初始化节点的值。
然后创建一个函数来将元素推入给定的链表中。
我们使用以上方法创建了一个链表，然后我们将最后一个节点链接到另一个节点，从而在其中形成一个循环。

弗洛伊德算法

在这个算法中，我们遍历整个链表，一旦进入链表，就不能从任何节点出去。这意味着如果我们对链表循环部分有两个指针，一个每次移动一个节点，另一个每次移动两个节点，它们将在某一点相遇。

实现算法后，我们将调用该函数并检查循环是否存在
如果存在循环，我们将调用另一个函数来找到循环的长度。
否则，我们将返回并打印不存在循环。

示例

在下面的示例中，我们定义了一个链表并向其中添加8个节点。我们通过将节点8连接到节点4来在链表中创建一个循环。所以它形成了一个包含五个节点的循环。

// 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)