数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究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个节点不存在，则打印“不存在”，否则打印该节点的值。我们实现了两种方法，一种是使用while循环的迭代方法，另一种是递归方法。两种方法的时间复杂度均为O(N)，但迭代方法更好，因为它不占用额外空间。
更新于：2023年5月4日
92 次浏览
广告