用 JavaScript 實現鏈表操作 - 03 Get Nth Node

syoya 發布于2019-08-21 14:53 / 1600人閱讀

摘要：獲得鏈表的第個節點。需求實現一個方法，傳入一個鏈表和一個索引，返回索引代表的節點。遞歸版本假設函數定義為，遞歸過程為當為零，直接返回該節點，否則遞歸調用。如果循環結束還沒有查到節點，那肯定是鏈表或者索引不合法，直接拋異常即可。

TL;DR

獲得鏈表的第 N 個節點。系列目錄見前言和目錄。

需求

實現一個 getNth() 方法，傳入一個鏈表和一個索引，返回索引代表的節點。索引以 0 為起始，第一個元素索引為 0 ，第二個為 1 ，以此類推。比如：

getNth(1 -> 2 -> 3 -> null, 0).data === 1
getNth(1 -> 2 -> 3 -> null, 1).data === 2

傳入的索引必須是在效范圍內，即 0..length-1 ，如果索引不合法或者鏈表為空都需要拋出異常。

遞歸版本

假設函數定義為 getNth(head, idx) ，遞歸過程為：當 idx 為零，直接返回該節點，否則遞歸調用 getNth(head.next, idx - 1) 。再處理下邊界情況就完成了，代碼如下：

function getNth(head, idx) {
  if (!head || idx < 0) throw "invalid argument"
  if (idx === 0) return head
  return getNth(head.next, idx - 1)
}

循環版本

我選擇的 for 循環，這樣方便把邊界情況檢查都放到循環里去。如果循環結束還沒有查到節點，那肯定是鏈表或者索引不合法，直接拋異常即可。對比這兩個版本和 02 Length & Count 的例子，不難看出循環可以比遞歸更容易地處理邊界情況，因為一些條件檢查可以寫進循環的頭部，遞歸就得自己寫 if/else 邏輯。

function getNthV2(head, idx) {
  for (let node = head; node && idx >= 0; node = node.next, idx--) {
    if (idx === 0) return node
  }
  throw "invalid argument"
}

參考資料

Codewars Kata
GitHub 的代碼實現
GitHub 的測試

GPU云服務器云服務器用javascript操作xml 多鏈表c語言實現 java實現鏈表插入遍歷c語言實現鏈表

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/88049.html

用 JavaScript 實現鏈表操作 - 前言和目錄

摘要：我打算寫一個鏈表操作的系列，來自的系列，實現語言是。通過自己實現一個鏈表和常用操作，可以加深理解這類數據結構的優缺點。鏈表經常用來訓練指針操作，雖然這只對適用，但等高級語言中控制引用的思路其實也差不多。 TL;DR 我打算寫一個鏈表操作的系列，來自 Codewars 的 Linked List 系列 kata ，實現語言是 JavaScript 。這篇是開篇，簡單描述了一下我寫這個的目...

BetaRabbit 2019-08-20 12:25 評論0 收藏0
用 JavaScript 實現鏈表操作 - 04 Insert Nth Node

摘要：給定一個鏈表，一個范圍在內的索引號，和一個數據，這個函數會生成一個新的節點并插入到指定的索引位置，并始終返回鏈表的頭。的返回值一定是個鏈表，我們把它賦值給就行。但這個例子的邊界情況是返回值不同如果，返回新節點。 TL;DR 插入第 N 個節點。系列目錄見前言和目錄。需求實現一個 insertNth() 方法，在鏈表的第 N 個索引處插入一個新節點。 insertNth() 可以...

894974231 2019-08-22 10:50 評論0 收藏0
leetcode-019-刪除鏈表倒數第N個結點(Remove Nth Node From End

摘要：第題給定一個鏈表，刪除鏈表的倒數第個節點，并且返回鏈表的頭結點。因為，若有一個真正的頭結點，則所有的元素處理方式都一樣。但以第一個有效元素為頭結點，就導致算法的不一致，需要單獨處理第一個有效元素頭結點。 leetcode第19題 Given a linked list, remove the n-th node from the end of list and return its h...

brianway 2019-08-23 14:34 評論0 收藏0
用 JavaScript 實現鏈表操作 - 11 Alternating Split

摘要：需求實現一個函數，把一個鏈表切分成兩個。子鏈表的節點應該是在父鏈表中交替出現的。所以整個算法的解法就能很容易地用表示。唯一需要考慮的就是在每個循環體中判斷節點該插入哪個鏈表。也有人使用持續增長的配合取余來做，比如。 TL;DR 把一個鏈表交替切分成兩個，系列目錄見前言和目錄。需求實現一個 alternatingSplit() 函數，把一個鏈表切分成兩個。子鏈表的節點應該是在父鏈...

jsyzchen 2019-08-20 14:02 評論0 收藏0
leetcode19 Remove Nth Node From End of List 從鏈表中移除

摘要：雖然時間復雜度還是但是顯然我們可以再一次遍歷中完成這個任務。現在跳出下標的思路，從另一個角度分析。快慢節點之間的距離始終是。當快節點到達終點時，此時的慢節點就是所要刪去的節點。題目要求 Given a linked list, remove the nth node from the end of list and return its head. For example, ...

YPHP 2019-08-14 18:05 評論0 收藏0