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

資訊專欄INFORMATION COLUMN

用 JavaScript 實現鏈表操作 - 13 Shuffle Merge

shiguibiao / 827人閱讀

摘要：需求實現函數把兩個鏈表合并成一個。新鏈表的節點是交叉從兩個鏈表中取的。通過行的調換指針，我們可以保證下一次循環就是對另一個鏈表進行操作了。這樣一直遍歷到兩個鏈表末尾，返回結束。參考資料的代碼實現的測試

TL;DR

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

需求

實現函數 shuffleMerge() 把兩個鏈表合并成一個。新鏈表的節點是交叉從兩個鏈表中取的。這叫洗牌合并。舉個例子，當傳入的鏈表為 1 -> 2 -> 3 -> null 和 7 -> 13 -> 1 -> null 時，合并后的鏈表為 1 -> 7 -> 2 -> 13 -> 3 -> 1 -> null 。如果合并過程中一個鏈表的數據先取完了，就從另一個鏈表中取剩下的數據。這個函數應該返回一個新鏈表。

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

如果參數之一為空，應該直接返回另一個鏈表（即使另一個鏈表也為空），不需要拋異常。

遞歸解法 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
}

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

遞歸解法 2

在上面的基礎上我們還能做個更聰明的版本，代碼如下：

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

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

循環解法

循環其實才是本題的考點，因為這題主要是考指針（引用）操作。尤其是把 “依次移動兩個鏈表的指針” 寫進一個循環里。不過上個解法中調換兩個鏈表順序的方式也可以用到這里。代碼如下：

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
}

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

參考資料

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

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

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

相關文章

  • 用 JavaScript 實現鏈表操作 - 14 Sorted Merge

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

    jzman 評論0 收藏0

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

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

    BetaRabbit 評論0 收藏0

  • 用 JavaScript 實現鏈表操作 - 15 Merge Sort

    摘要：需求實現函數進行歸并排序。解法歸并排序的運行方式是，遞歸的把一個大鏈表切分成兩個小鏈表。切分到最后就全是單節點鏈表了，而單節點鏈表可以被認為是已經排好序的。這時候再兩兩合并，最終會得到一個完整的已排序鏈表。用把排好序的兩個鏈表合并起來。 TL;DR 對鏈表進行歸并排序，系列目錄見 前言和目錄 。 需求 實現函數 mergeSort() 進行歸并排序。注意這種排序法需要使用遞歸。在 fr...

    X_AirDu 評論0 收藏0

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

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

    zhou_you 評論0 收藏0

發表評論

0條評論

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