数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究JavaScript 查找循环链表长度的程序
在本程序中，我们将得到一个可能包含循环的链表，我们必须找到如果存在循环，那么循环的大小是多少。让我们用代码来介绍一种非常著名的查找循环长度的方法，并讨论其时间和空间复杂度。
问题介绍
在这个问题中，如上所述，我们得到一个可能包含或不包含循环的链表，如果存在循环，我们必须找到循环的长度，否则我们必须返回零，因为不存在循环。我们将使用 Floyd 循环方法来查找循环，然后检查其大小。例如，如果我们得到一个如下所示的链表：
List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
并且从包含 8 的节点到包含 4 的节点存在一个循环，这意味着 8 连接到 4，形成长度为 5 的循环，我们必须检测到它。
方法
在这个问题中，我们将使用 Floyd 循环方法来检测循环，然后我们将使用长度查找的概念来查找循环的长度。让我们首先了解问题的基本步骤，然后我们将转向 Floyd 方法和长度方法。
首先，我们将创建类以提供链表节点的基本结构，并在其中定义构造函数以初始化节点值。
然后，我们创建了一个函数来将元素推入给定的链表。
我们使用上述方法创建了一个链表，然后我们将最后一个节点链接到另一个节点，以在其内部创建一个循环。
Floyd 算法
在这个算法中，我们遍历链表，一旦我们进入链表循环部分，我们就无法从任何节点离开。这意味着如果我们在该链表循环部分有两个指针，一个指针每次向前移动一个节点，另一个指针每次向前移动两个节点，它们将在某个点相遇。
在实现算法之后，我们将调用该函数并检查循环是否存在。
如果循环存在，我们将调用另一个函数来查找循环的长度。
否则，我们将返回并打印不存在循环。
示例
在下面的示例中，我们定义了一个链表并向其中添加了 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)。
122 次查看
