用 JavaScript 實現鏈表操作 - 04 Insert Nth Node

894974231 發布于2019-08-22 10:50 / 1601人閱讀

摘要：給定一個鏈表，一個范圍在內的索引號，和一個數據，這個函數會生成一個新的節點并插入到指定的索引位置，并始終返回鏈表的頭。的返回值一定是個鏈表，我們把它賦值給就行。但這個例子的邊界情況是返回值不同如果，返回新節點。

TL;DR

插入第 N 個節點。系列目錄見前言和目錄。

需求

實現一個 insertNth() 方法，在鏈表的第 N 個索引處插入一個新節點。

insertNth() 可以看成是 01 Push & Build List 中的 push() 函數的更通用版本。給定一個鏈表，一個范圍在 0..length 內的索引號，和一個數據，這個函數會生成一個新的節點并插入到指定的索引位置，并始終返回鏈表的頭。

insertNth(1 -> 2 -> 3 -> null, 0, 7) === 7 -> 1 -> 2 -> 3 -> null)
insertNth(1 -> 2 -> 3 -> null, 1, 7) === 1 -> 7 -> 2 -> 3 -> null)
insertNth(1 -> 2 -> 3 -> null, 3, 7) === 1 -> 2 -> 3 -> 7 -> null)

如果索引號超出了鏈表的長度，函數應該拋出異常。

實現這個函數允許使用第一個 kata 中的 push 方法。

遞歸版本

讓我們先回憶一下 push 函數的用處，指定一個鏈表的頭和一個數據，push 會生成一個新節點并添加到鏈表的頭部，并返回新鏈表的頭。比如：

push(null, 23) === 23 -> null
push(1 -> 2 -> null, 23) === 23 -> 1 -> 2 -> null

現在看看 insertNth ，假設函數方法簽名是 insertNth(head, index, data) ，那么有兩種情況：

如果 index === 0 ，則等同于調用 push 。實現為 push(head, data) 。

如果 index !== 0 ，我們可以把下一個節點當成子鏈表傳入 insertNth ，并讓 index 減一。insertNth 的返回值一定是個鏈表，我們把它賦值給 head.next 就行。這就是一個遞歸過程。如果這次遞歸的 insertNth 完不成任務，它會繼續遞歸到下一個節點，直到 index === 0 的最簡單情況，或 head 為空拋出異常（索引過大）。

完整代碼實現為：

function insertNth(head, index, data) {
  if (index === 0) return push(head, data)
  if (!head) throw "invalid argument"
  head.next = insertNth(head.next, index - 1, data)
  return head
}

循環版本

如果能理解遞歸版本的 head.next = insertNth(...) ，那么循環版本也不難實現。不同的是，在循環中我們遍歷到 index 的前一個節點，然后用 push 方法生成新節點，并賦值給前一個節點的 next 屬性形成一個完整的鏈表。

完整代碼實現如下：

function insertNthV2(head, index, data) {
  if (index === 0) return push(head, data)

  for (let node = head, idx = 0; node; node = node.next, idx++) {
    if (idx + 1 === index) {
      node.next = push(node.next, data)
      return head
    }
  }

  throw "invalid argument"
}

這里有一個邊界情況要注意。因為 insertNth 要求返回新鏈表的頭。根據 index 是否為 0 ，這個新鏈表的頭可能是生成的新節點，也可能就是老鏈表的頭。這點如果寫進 for 循環就不可避免有 if/else 的返回值判斷。所以我們把 index === 0 的情況多帶帶拿出來放在函數頂部。這個邊界情況并非無法納入循環中，我們下面介紹的一個技巧就與此有關。

循環版本 - dummy node

在之前的幾個 kata 里，我們提到循環可以更好的容納邊界情況，因為一些條件判斷都能寫到 for 的頭部中去。但這個例子的邊界情況是返回值不同：

如果 index === 0 ，返回新節點。

如果 index !== 0 ，返回 head 。新節點會被插入 head 之后的某個節點鏈條中。

如何解決這個問題呢，我們可以在 head 前面再加入一個節點（數據任意，一般賦值 null）。這個節點稱為 dummy 節點。這樣一來，不管新節點插入到哪里，dummy.next 都可以引用到修改后的鏈表。

代碼實現如下，注意 return 的不同。

function insertNthV3(head, index, data) {
  const dummy = push(head, null)

  for (let node = dummy, idx = 0; node; node = node.next, idx++) {
    if (idx === index) {
      node.next = push(node.next, data)
      return dummy.next
    }
  }

  throw "invalid argument"
}

dummy 節點是很多鏈表操作的常用技巧，雖然在這個 kata 中使用 dummy 節點的代碼量并沒有變少，但這個技巧在后續的一些復雜 kata 中會非常有用。

參考資料

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

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

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

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

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

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

BetaRabbit 2019-08-20 12:25 評論0 收藏0
JavaScript數據結構04 - 鏈表

摘要：類表示要加入鏈表的項。循環鏈表和普通鏈表之間唯一的區別在于，最后一個元素指向下一個元素的指針不是引用，而是指向第一個元素。這里就不進行代碼實現了，大家可以結合上面的單向鏈表和雙向鏈表自己實現一個循環鏈表。一、定義 1.1 概念前面我們學習了數組這種數據結構。數組（或者也可以稱為列表）是一種非常簡單的存儲數據序列的數據結構。在這一節，我們要學習如何實現和使用鏈表這種動態的數據結構，這...

cheukyin 2019-08-23 10:39 評論0 收藏0
用 JavaScript 實現鏈表操作 - 11 Alternating Split

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

jsyzchen 2019-08-20 14:02 評論0 收藏0
用 JavaScript 實現鏈表操作 - 03 Get Nth Node

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

syoya 2019-08-21 14:53 評論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