成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

用 JavaScript 實現(xiàn)鏈表操作 - 04 Insert Nth Node

894974231 / 1608人閱讀

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

TL;DR

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

需求

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

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

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)

如果索引號超出了鏈表的長度，函數(shù)應(yīng)該拋出異常。

實現(xiàn)這個函數(shù)允許使用第一個 kata 中的 push 方法。

遞歸版本

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

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

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

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

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

完整代碼實現(xiàn)為：

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
}
循環(huán)版本

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

完整代碼實現(xiàn)如下：

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 要求返回新鏈表的頭。根據(jù) index 是否為 0 ，這個新鏈表的頭可能是生成的新節(jié)點，也可能就是老鏈表的頭 。這點如果寫進 for 循環(huán)就不可避免有 if/else 的返回值判斷。所以我們把 index === 0 的情況多帶帶拿出來放在函數(shù)頂部。這個邊界情況并非無法納入循環(huán)中，我們下面介紹的一個技巧就與此有關(guān)。

循環(huán)版本 - dummy node

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

如果 index === 0 ，返回新節(jié)點 。

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

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

代碼實現(xiàn)如下，注意 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 節(jié)點是很多鏈表操作的常用技巧，雖然在這個 kata 中使用 dummy 節(jié)點的代碼量并沒有變少，但這個技巧在后續(xù)的一些復(fù)雜 kata 中會非常有用。

參考資料

Codewars Kata
GitHub 的代碼實現(xiàn)
GitHub 的測試

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/91358.html

相關(guān)文章

  • 用 JavaScript 實現(xiàn)鏈表操作 - 前言和目錄

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

    BetaRabbit 評論0 收藏0

  • JavaScript數(shù)據(jù)結(jié)構(gòu)04 - 鏈表

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

    cheukyin 評論0 收藏0

  • 用 JavaScript 實現(xiàn)鏈表操作 - 11 Alternating Split

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

    jsyzchen 評論0 收藏0

  • 用 JavaScript 實現(xiàn)鏈表操作 - 03 Get Nth Node

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

    syoya 評論0 收藏0

  • leetcode-019-刪除鏈表倒數(shù)第N個結(jié)點(Remove Nth Node From End

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

    brianway 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<