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

链表是一种可以变长的线性数据结构，链表的长度是可以改变的，这就是数组中数组长度不能改变的问题。在本文中，我们将通过实现代码并检查边缘情况来找到给定链表的长度。我们将在本文中使用 while 循环和类概念。

问题简介

在给定的问题中，我们得到一个链表，首先，我们必须使用类创建链表，然后我们必须找到给定链表的长度。由于链表的长度是可以改变的，所以我们会在特定的代码点找到链表的长度。

我们将使用两种方法，首先是使用 while 循环的直接迭代方法，另一种是递归方法来查找给定链表的长度。

迭代方法

在此方法中，我们将首先使用类为链表提供结构来创建一个链表。我们将定义一些函数，例如push函数，通过简单地传递头和数据来将值添加到链表中。

示例

在此过程中，我们将使用 while 循环、链表的头或起始节点以及一个变量来计算链表中的节点数，即给定链表的长度。

// creating the linked list node
class Node{
   constructor(data)  {
      this.value = data;
      this.next = null;
   }
}
function push(tail, data){
   var new_node = new Node(data);
   tail.next = new_node;
   tail = tail.next;
   return tail
}
function length(head){
   temp = head;
   var count = 0
   while(temp != null) {
      count++;
      temp = temp.next;
   }
   return count;
}
var head = new Node(1);
var tail = head;
tail = push(tail, 2)
tail = push(tail, 3)
tail = push(tail, 4)
tail = push(tail, 5)
tail = push(tail, 6)
console.log("Length of the given linked list is: " + length(head))

在上面给出的方法中，我们没有使用任何额外的空间，并且只遍历链表一次。因此，上述方法的时间复杂度为 O(N)，其中 N 是链表的大小，上述方法的空间复杂度为 O(1)。

递归方法

在此方法中，我们将遵循与上述方法中创建链表相同的步骤，对于主要任务，我们将使用递归方法。

示例

使用与函数本身不同的参数和特定的基本条件调用相同的函数称为递归。在此方法中，我们将使用链表的头调用该函数，然后从该函数中，我们将再次调用该函数，但参数为当前节点的下一个节点。作为返回值，我们将返回 1 + 递归调用返回值，并且结果将在第一次调用时给出。让我们看看代码 -

// creating the linked list node
class Node {
   constructor(data) {
      this.value = data;
      this.next = null;
   }
}
function push(tail, data) {
   var new_node = new Node(data);
   tail.next = new_node;
   tail = tail.next;
   return tail
}

function length(cur) {
   if(cur == null) return 0;
   return 1 + length(cur.next);
}
var head = new Node(1);
var tail = head;
tail = push(tail, 2)
tail = push(tail, 3)
tail = push(tail, 4)
tail = push(tail, 5)
tail = push(tail, 6)
console.log("Length of the given linked list is: " + length(head))

时间和空间复杂度

递归方法的时间复杂度为 O(N)，其中 N 是给定链表中存在的节点数。上面代码的空间复杂度是O(N)，因为总共有N次调用，并且对于每次调用，我们都必须维护当前的节点堆栈。

结论

在本教程中，我们学习了如何通过实现代码并研究边缘情况来查找给定链表的长度。我们在第一种方法中使用了本文中的 while 循环和类概念，在第二种方法中使用了递归方法来查找长度。两种方法的时间复杂度均为 O(N)，其中 N 是链表的长度，而由于堆栈大小，递归方法的空间复杂度为 O(N)。

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