用於編寫獲取鍊錶中第 N 個節點的函數的 JavaScript 程式

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