国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專(zhuān)欄INFORMATION COLUMN

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

jsyzchen / 3296人閱讀

摘要：需求實(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)該是在父鏈表中交替出現(xiàn)的。如果原鏈表是 a -> b -> a -> b -> a -> null ，則兩個(gè)子鏈表分別為 a -> a -> a -> null 和 b -> b -> null 。

var list = 1 -> 2 -> 3 -> 4 -> 5 -> null
alternatingSplit(list).first === 1 -> 3 -> 5 -> null
alternatingSplit(list).second === 2 -> 4 -> null

為了簡(jiǎn)化結(jié)果，函數(shù)會(huì)返回一個(gè) Context 對(duì)象來(lái)保存兩個(gè)子鏈表，Context 結(jié)構(gòu)如下所示：

function Context(first, second) {
  this.first = first
  this.second = second
}

如果原鏈表為 null 或者只有一個(gè)節(jié)點(diǎn)，應(yīng)該拋出異常。

遞歸版本

代碼如下：

function alternatingSplit(head) {
  if (!head || !head.next) throw new Error("invalid arguments")
  return new Context(split(head), split(head.next))
}

function split(head) {
  const list = new Node(head.data)
  if (head.next && head.next.next) list.next = split(head.next.next)
  return list
}

這個(gè)解法的核心思路在于 split ，這個(gè)方法接收一個(gè)鏈表并返回一個(gè)以奇數(shù)位的節(jié)點(diǎn)組成的子鏈表。所以整個(gè)算法的解法就能很容易地用 new Context(split(head), split(head.next)) 表示。

另一個(gè)遞歸版本

代碼如下：

function alternatingSplitV2(head) {
  if (!head || !head.next) throw new Error("invalid arguments")
  return new Context(...splitV2(head))
}

function splitV2(head) {
  if (!head) return [null, null]

  const first = new Node(head.data)
  const [second, firstNext] = splitV2(head.next)
  first.next = firstNext
  return [first, second]
}

這里的 splitV2 的作用跟整個(gè)算法的含義一樣 -- 接收一個(gè)鏈表并返回交叉分割的兩個(gè)子鏈表（以數(shù)組表示）。第一個(gè)子鏈表的頭自然是 new Node(head.data) ，第二個(gè)子鏈表呢？它其實(shí)是 splitV2(head.next) 的第一個(gè)子鏈表（見(jiàn)第 4 行）。理解這個(gè)邏輯后就能明白遞歸過(guò)程。

循環(huán)版本

代碼如下：

function alternatingSplitV3(head) {
  if (!head || !head.next) throw new Error("invalid arguments")

  const first = new Node()
  const second = new Node()
  const tails = [first, second]

  for (let node = head, idx = 0; node; node = node.next, idx = idx ? 0 : 1) {
    tails[idx].next = new Node(node.data)
    tails[idx] = tails[idx].next
  }

  return new Context(first.next, second.next)
}

這個(gè)思路是，先用兩個(gè)變量代表子鏈表，然后對(duì)整個(gè)鏈表進(jìn)行一次遍歷，分別把節(jié)點(diǎn)交替插入每個(gè)子鏈表中。唯一需要考慮的就是在每個(gè)循環(huán)體中判斷節(jié)點(diǎn)該插入哪個(gè)鏈表。我用的是 idx 變量，在每輪循環(huán)中把它交替設(shè)置成 0 和 1 。也有人使用持續(xù)增長(zhǎng)的 idx 配合取余來(lái)做，比如 idx % 2 。做法有很多種，就不贅述了。

這里也用了 dummy node 的技巧來(lái)簡(jiǎn)化 “判斷首節(jié)點(diǎn)是否為空” 的情況。關(guān)于這個(gè)技巧可以看看 Insert Nth Node

參考資料

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

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/81377.html

相關(guān)文章

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

    摘要：我打算寫(xiě)一個(gè)鏈表操作的系列，來(lái)自的系列，實(shí)現(xiàn)語(yǔ)言是。通過(guò)自己實(shí)現(xiàn)一個(gè)鏈表和常用操作，可以加深理解這類(lèi)數(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í)現(xiàn)鏈表操作 - 12 Front Back Split

    摘要：需求實(shí)現(xiàn)函數(shù)把鏈表居中切分成兩個(gè)子鏈表一個(gè)前半部分，另一個(gè)后半部分。提示一個(gè)簡(jiǎn)單的做法是計(jì)算鏈表的長(zhǎng)度，然后除以得出前半部分的長(zhǎng)度，最后分割鏈表。最后用把數(shù)組轉(zhuǎn)回鏈表。參考資料的代碼實(shí)現(xiàn)的測(cè)試 TL;DR 把一個(gè)鏈表居中切分成兩個(gè)，系列目錄見(jiàn) 前言和目錄 。 需求 實(shí)現(xiàn)函數(shù) frontBackSplit() 把鏈表居中切分成兩個(gè)子鏈表 -- 一個(gè)前半部分，另一個(gè)后半部分。如果節(jié)點(diǎn)數(shù)為奇...

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

  • 用 JavaScript 實(shí)現(xiàn)鏈表操作 - 15 Merge Sort

    摘要：需求實(shí)現(xiàn)函數(shù)進(jìn)行歸并排序。解法歸并排序的運(yùn)行方式是，遞歸的把一個(gè)大鏈表切分成兩個(gè)小鏈表。切分到最后就全是單節(jié)點(diǎn)鏈表了，而單節(jié)點(diǎn)鏈表可以被認(rèn)為是已經(jīng)排好序的。這時(shí)候再兩兩合并，最終會(huì)得到一個(gè)完整的已排序鏈表。用把排好序的兩個(gè)鏈表合并起來(lái)。 TL;DR 對(duì)鏈表進(jìn)行歸并排序，系列目錄見(jiàn) 前言和目錄 。 需求 實(shí)現(xiàn)函數(shù) mergeSort() 進(jìn)行歸并排序。注意這種排序法需要使用遞歸。在 fr...

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

  • 用 JavaScript 實(shí)現(xiàn)鏈表操作 - 13 Shuffle Merge

    摘要：需求實(shí)現(xiàn)函數(shù)把兩個(gè)鏈表合并成一個(gè)。新鏈表的節(jié)點(diǎn)是交叉從兩個(gè)鏈表中取的。通過(guò)行的調(diào)換指針，我們可以保證下一次循環(huán)就是對(duì)另一個(gè)鏈表進(jìn)行操作了。這樣一直遍歷到兩個(gè)鏈表末尾，返回結(jié)束。參考資料的代碼實(shí)現(xiàn)的測(cè)試 TL;DR 把兩個(gè)鏈表洗牌合并成一個(gè)，系列目錄見(jiàn) 前言和目錄 。 需求 實(shí)現(xiàn)函數(shù) shuffleMerge() 把兩個(gè)鏈表合并成一個(gè)。新鏈表的節(jié)點(diǎn)是交叉從兩個(gè)鏈表中取的。這叫洗牌合并。舉...

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

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

0條評(píng)論

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