用于编写获取链表中第 N 个节点的函数的 JavaScript 程序

链表是一种线性数据结构，所有节点通过存储下一个节点的地址相互连接。查找链表中的第n个节点意味着获取给定链表中第n个节点的值，可以通过迭代和递归两种方法来完成。

示例

Given linked list: 
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
Node to find: 3

输出

3

说明：第三个节点的值为 3。

迭代方法

在这种方法中，我们将使用 while 循环直接遍历链表，直到到达最后一个节点或所需的节点。

示例

// class to create the structure of the nodes 
class Node{
   constructor(data){
      this.value = data;
      this.next = null;
   }
}

// function to print the linked list
function print(head){
   var temp = head;
   var ans = ""
   while(temp.next != null){
      ans += temp.value;
      ans += " -> "
      temp = temp.next
   }
   ans += temp.value
   ans += " -> null"
   console.log(ans)
}

// function to add data in linked list 
function add(data, head, tail){
   return tail.next = new Node(data);
}

// function to find the nth node 
function findNode(head, node){
   var temp = head;
   while(node > 1 && temp != null){
      node--;
      temp = temp.next;
   }
   return temp;
}

// defining linked list
var head  = new Node(1)
var tail  = head
tail = add(2,head, tail)
tail = add(3,head, tail)
tail = add(4,head, tail)
tail = add(5,head, tail)
tail = add(6,head, tail)
tail = add(7,head, tail)
tail = add(8,head, tail)

// printing linked list 
console.log("The given linked list is: ")
print(head)

// defining node to get 
var node = 5;

// calling function to get the nth node; 
var nth_node = findNode(head,node)
if(nth_node == null){
   console.log("The given linked list does not have the Nth Node");
}
else{
   console.log("The value present at the nth node is: " + nth_node.value);
}

输出

The given linked list is: 
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> null
The value present at the nth node is: 5

时间和空间复杂度

上述代码的时间复杂度为O(N)，其中N是给定链表的大小。这里给定的数字可能小于给定链表的大小，但在最坏的情况下，我们只会遍历链表的长度。

这里我们没有使用任何额外的空间，这意味着上面代码的时间复杂度是 O(1)。

递归方法

在这种方法中，我们将使用递归调用而不是 while 循环来遍历链表，并实现前面的逻辑。

示例

// class to create the structure of the nodes 
class Node{
   constructor(data){
      this.value = data;
      this.next = null;
   }
}

// function to print the linked list
function print(head){
   var temp = head;
   var ans = ""
   while(temp.next != null){
      ans += temp.value;
      ans += " -> "
      temp = temp.next
   }
   ans += temp.value
   ans += " -> null"
   console.log(ans)
}

// function to add data in linked list 
function add(data, head, tail){
   return tail.next = new Node(data);    
}

// function to find the nth node 
function findNode(head, node){
   if(node == 1){
      return head;
   }
   else if(head == null){
      return null;
   }
   else{
      return findNode(head.next, node-1);
   }
}

// defining linked list
var head  = new Node(1)
var tail  = head
tail = add(2,head, tail)
tail = add(3,head, tail)
tail = add(4,head, tail)
tail = add(5,head, tail)
tail = add(6,head, tail)
tail = add(7,head, tail)
tail = add(8,head, tail)

// printing linked list 
console.log("The given linked list is: ")
print(head)

// defining node to get 
var node = 9;

// calling function to get the nth node; 
var nth_node = findNode(head,node)
if(nth_node == null){
   console.log("The given linked list does not have the " + node + " number of nodes");
}
else{
   console.log("The value present at the nth node is: " + nth_node.value);
}

输出

The given linked list is: 
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> null
The given linked list does not have the 9 number of nodes

时间和空间复杂度

上述代码的时间和空间复杂度相同，均为 O(N)，其中 N 是给定链表中的节点数。这里的空间是由于递归调用造成的。

结论

在本教程中，我们实现了一个 JavaScript 程序来查找给定链表中的第 n 个节点。如果第 n 个节点不存在，则我们打印不存在，否则打印该节点处存在的值。我们实现了两种方法，一种是使用 while 循环的迭代，另一种是递归方法。两者的时间复杂度都是 O(N)，但迭代更好，因为它不需要额外的空间。