极客笔记JavaScript 编写一个获得链表中第N个节点的函数的程序
链表是一种线性数据结构，所有的节点通过存储下一个节点的地址来相互连接。要在链表中找到第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个节点不存在，则打印“not present”，否则打印该节点的值。我们实现了两种方法，一种是使用while循环的迭代方法，另一种是递归方法。两种方法的时间复杂度均为O(N)，但迭代方法更好，因为它不需要额外的空间。