链表是一种线性数据结构，所有节点通过存储下一个节点的地址相互连接。查找链表中的第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)，但迭代更好，因为它不需要额外的空间。
想要了解更多内容，请持续关注码农资源网，一起探索发现编程世界的无限可能!
本站部分资源来源于网络，仅限用于学习和研究目的，请勿用于其他用途。
如有侵权请发送邮件至1943759704@qq.com删除
码农资源网 » 用于编写获取链表中第 N 个节点的函数的 JavaScript 程序
本站部分资源来源于网络，仅限用于学习和研究目的，请勿用于其他用途。
如有侵权请发送邮件至1943759704@qq.com删除
码农资源网 » 用于编写获取链表中第 N 个节点的函数的 JavaScript 程序
