亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

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

894974231 / 1656人閱讀

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

TL;DR

插入第 N 個(gè)節(jié)點(diǎn)。系列目錄見(jiàn) 前言和目錄 。

需求

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

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

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)

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

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

遞歸版本

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

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 。實(shí)現(xiàn)為 push(head, data) 。

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

完整代碼實(shí)現(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)版本也不難實(shí)現(xiàn)。不同的是，在循環(huán)中我們遍歷到 index 的前一個(gè)節(jié)點(diǎn)，然后用 push 方法生成新節(jié)點(diǎn)，并賦值給前一個(gè)節(jié)點(diǎn)的 next 屬性形成一個(gè)完整的鏈表。

完整代碼實(shí)現(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"
}

這里有一個(gè)邊界情況要注意。因?yàn)?insertNth 要求返回新鏈表的頭。根據(jù) index 是否為 0 ，這個(gè)新鏈表的頭可能是生成的新節(jié)點(diǎn)，也可能就是老鏈表的頭 。這點(diǎn)如果寫(xiě)進(jìn) for 循環(huán)就不可避免有 if/else 的返回值判斷。所以我們把 index === 0 的情況多帶帶拿出來(lái)放在函數(shù)頂部。這個(gè)邊界情況并非無(wú)法納入循環(huán)中，我們下面介紹的一個(gè)技巧就與此有關(guān)。

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

在之前的幾個(gè) kata 里，我們提到循環(huán)可以更好的容納邊界情況，因?yàn)橐恍l件判斷都能寫(xiě)到 for 的頭部中去。但這個(gè)例子的邊界情況是返回值不同：

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

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

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

代碼實(shí)現(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é)點(diǎn)是很多鏈表操作的常用技巧，雖然在這個(gè) kata 中使用 dummy 節(jié)點(diǎn)的代碼量并沒(méi)有變少，但這個(gè)技巧在后續(xù)的一些復(fù)雜 kata 中會(huì)非常有用。

參考資料

Codewars Kata
GitHub 的代碼實(shí)現(xiàn)
GitHub 的測(cè)試

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/91358.html

相關(guān)文章

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

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

    BetaRabbit 評(píng)論0 收藏0

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

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

    cheukyin 評(píng)論0 收藏0

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

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

    jsyzchen 評(píng)論0 收藏0

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

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

    syoya 評(píng)論0 收藏0

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

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

    brianway 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<