链表是一种线性数据结构,所有节点通过存储下一个节点的地址相互连接。查找链表中的第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),但迭代更好,因为它不需要额外的空间。
以上就是用于编写获取链表中第 N 个节点的函数的 JavaScript 程序的详细内容,更多请关注php中文网其它相关文章!
已抢23786个
抢已抢118307个
抢已抢139541个
抢已抢6344个
抢已抢36685个
抢已抢66987个
抢