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

在这个程序中，我们将得到一个可能包含循环的链表，我们必须找出循环是否存在，然后循环的大小是多少。让我们使用一个非常著名的方法来借助代码来查找循环的长度，并讨论其时间和空间复杂度。

问题简介

在这个问题中，正如我们上面所看到的，我们给出了一个链表，其中可能包含也可能不包含循环，如果循环存在，我们必须找到循环的长度，否则我们必须返回零，因为有不存在循环。我们将使用 Floyd 循环方法来查找循环，然后检查其大小。例如，如果我们给出一个链表 -

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

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

方法

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

• 首先，我们将创建一个类来提供链表节点的基本结构，并在其中定义构造函数来初始化节点值。

• 然后我们创建了一个函数来将元素推送到给定的链表中。

• 我们使用上面的方法创建了一个链表，然后将最后一个节点链接到另一个节点以在其中形成一个循环。

弗洛伊德算法

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

• 实现算法后，我们将调用该函数并检查循环是否存在

• 如果存在循环，我们将调用 anther 函数来查找循环的长度。

• 另一方面，我们将返回并打印不存在循环。

示例

在下面的示例中，我们定义一个链表并向其中添加 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)

时间和空间复杂度

在上面的代码中，我们只遍历了完整的链表一次，循环部分最多遍历了三次，这使得时间复杂度是线性的。因此上述代码的时间复杂度是线性的，即 O(N)，其中 N 是链表的大小。

由于我们没有使用任何额外的空间，使得程序的时间复杂度为 O(1)。

结论

在本教程中，我们学习了如何通过在 JavaScript 语言中实现概念来查找链表中存在的循环的长度。我们使用了 Floyd 的循环查找算法来查找给定链表中的循环，然后我们使用 while 循环来遍历循环并找到其长度。上述代码的时间复杂度为O(N)，空间复杂度为O(1)。

以上是用于查找链表中循环长度的 JavaScript 程序的详细内容。更多信息请关注PHP中文网其他相关文章！