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

資訊專欄INFORMATION COLUMN

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

shiguibiao / 833人閱讀

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

TL;DR

把兩個(gè)鏈表洗牌合并成一個(gè)，系列目錄見 前言和目錄 。

需求

實(shí)現(xiàn)函數(shù) shuffleMerge() 把兩個(gè)鏈表合并成一個(gè)。新鏈表的節(jié)點(diǎn)是交叉從兩個(gè)鏈表中取的。這叫洗牌合并。舉個(gè)例子，當(dāng)傳入的鏈表為 1 -> 2 -> 3 -> null 和 7 -> 13 -> 1 -> null 時(shí)，合并后的鏈表為 1 -> 7 -> 2 -> 13 -> 3 -> 1 -> null 。如果合并過程中一個(gè)鏈表的數(shù)據(jù)先取完了，就從另一個(gè)鏈表中取剩下的數(shù)據(jù)。這個(gè)函數(shù)應(yīng)該返回一個(gè)新鏈表。

var first = 3 -> 2 -> 8 -> null
var second = 5 -> 6 -> 1 -> 9 -> 11 -> null
shuffleMerge(first, second) === 3 -> 5 -> 2 -> 6 -> 8 -> 1 -> 9 -> 11 -> null

如果參數(shù)之一為空，應(yīng)該直接返回另一個(gè)鏈表（即使另一個(gè)鏈表也為空），不需要拋異常。

遞歸解法 1

代碼如下：

function shuffleMerge(first, second) {
  if (!first || !second) return first || second

  const list = new Node(first.data, new Node(second.data))
  list.next.next = shuffleMerge(first.next, second.next)
  return list
}

解題思路是，首先判斷是否有一個(gè)鏈表為空，有就返回另一個(gè)，結(jié)束遞歸。這個(gè)判斷過了，下面肯定是兩個(gè)鏈表都不為空的情況。我們依次從兩個(gè)鏈表中取第一個(gè)節(jié)點(diǎn)組合成新鏈表，然后遞歸 shuffleMerge 兩個(gè)鏈表的后續(xù)節(jié)點(diǎn)，并把結(jié)果銜接到 list 后面。這段代碼基本跟題目描述的意思一致。

遞歸解法 2

在上面的基礎(chǔ)上我們還能做個(gè)更聰明的版本，代碼如下：

function shuffleMergeV2(first, second) {
  if (!first || !second) return first || second
  return new Node(first.data, shuffleMerge(second, first.next))
}

通過簡單的調(diào)換 first 和 second 的順序，我們能把遞歸過程從 “先取 first 的首節(jié)點(diǎn)再取 second 的首節(jié)點(diǎn)” 變成 “總總是取 first 的首節(jié)點(diǎn)” 。解法 1 中的三行代碼簡化成了一行。

循環(huán)解法

循環(huán)其實(shí)才是本題的考點(diǎn)，因?yàn)檫@題主要是考指針（引用）操作。尤其是把 “依次移動(dòng)兩個(gè)鏈表的指針” 寫進(jìn)一個(gè)循環(huán)里。不過上個(gè)解法中調(diào)換兩個(gè)鏈表順序的方式也可以用到這里。代碼如下：

function shuffleMergeV3(first, second) {
  const result = new Node()
  let pr = result
  let [p1, p2] = [first, second]

  while (p1 || p2) {
    if (p1) {
      pr.next = new Node(p1.data)
      pr = pr.next
      p1 = p1.next
    }
    [p1, p2] = [p2, p1]
  }

  return result.next
}

首先我們生成一個(gè) dummy node result ，同時(shí)建立一個(gè) pr 代表 result 的尾節(jié)點(diǎn)（方便插入）。兩個(gè)鏈表的指針分別叫 p1 和 p2 。在每次循環(huán)中我們都把 p1 的節(jié)點(diǎn)數(shù)據(jù)寫到 result 鏈表的末尾，然后修改指針指向下一個(gè)節(jié)點(diǎn)。通過 12 行的調(diào)換指針，我們可以保證下一次循環(huán)就是對另一個(gè)鏈表進(jìn)行操作了。這樣一直遍歷到兩個(gè)鏈表末尾，返回 result.next 結(jié)束。

參考資料

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

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

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

相關(guān)文章

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

    摘要：需求實(shí)現(xiàn)函數(shù)把兩個(gè)升序排列的鏈表合并成一個(gè)新鏈表，新鏈表也必須是升序排列的。有一些邊界情況要考慮或可能為，在合并過程中或的數(shù)據(jù)有可能先取完。第行的指針調(diào)換讓始終小于等于，從而避免了重復(fù)的代碼。參考資料的代碼實(shí)現(xiàn)的測試 TL;DR 把兩個(gè)升序排列的鏈表合并成一個(gè)，系列目錄見 前言和目錄 。 需求 實(shí)現(xiàn)函數(shù) sortedMerge() 把兩個(gè)升序排列的鏈表合并成一個(gè)新鏈表，新鏈表也必須是升...

    jzman 評論0 收藏0

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

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

    BetaRabbit 評論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è)鏈表合并起來。 TL;DR 對鏈表進(jìn)行歸并排序，系列目錄見 前言和目錄 。 需求 實(shí)現(xiàn)函數(shù) mergeSort() 進(jìn)行歸并排序。注意這種排序法需要使用遞歸。在 fr...

    X_AirDu 評論0 收藏0

  • LeetCode 之 JavaScript 解答第23題 —— 合并K個(gè)有序鏈表（Merge K S

    摘要：分治算法遞歸每層操作分解將原問題分解成一系列的子問題。分治算法滿足的條件可分解原問題與分解成的小問題具有相同的模式無關(guān)聯(lián)原問題分解成的子問題可以獨(dú)立求解，子問題之間沒有相關(guān)性，這一點(diǎn)是分治算法跟動(dòng)態(tài)規(guī)劃的明顯區(qū)別。 Time：2019/4/10Title: Merge K Sorted ListsDifficulty: DifficultyAuthor: 小鹿 題目：Merge K...

    zhou_you 評論0 收藏0

發(fā)表評論

0條評論

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