鍊錶是一種線性資料結構，所有節點透過儲存下一個節點的位址相互連接。尋找鍊錶中的第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中文網其他相關文章！
