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

jzman 發布于2019-08-20 14:21 / 2382人閱讀

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

TL;DR

把兩個升序排列的鏈表合并成一個，系列目錄見前言和目錄。

需求

實現函數 sortedMerge() 把兩個升序排列的鏈表合并成一個新鏈表，新鏈表也必須是升序排列的。這個函數應該對每個輸入的鏈表都只遍歷一次。

var first = 2 -> 4 -> 6 -> 7 -> null
var second = 1 -> 3 -> 5 -> 6 -> 8 -> null
sortedMerge(first, second) === 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 6 -> 7 -> 8 -> null

有一些邊界情況要考慮：first 或 second 可能為 null ，在合并過程中 first 或 second 的數據有可能先取完。如果一個鏈表為空，就返回另一個鏈表（即使它也為空），不需要拋出異常。

在做這個 kata 之前，建議先完成 Shuffle Merge 。

遞歸解法

代碼如下：

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

  if (first.data <= second.data) {
    return new Node(first.data, sortedMerge(first.next, second))
  } else {
    return new Node(second.data, sortedMerge(first, second.next))
  }
}

跟上個 kata 類似的思路。不過為了保證最后的結果是升序排列的，我們要取兩個鏈表中值更小的首節點，添加到結果鏈表的末尾。思路就不贅述了。

循環解法

循環是這個 kata 有意思的一點，很多邊界情況的判斷也發生在這里。很容易寫出這樣的 if/else ：

let [p1, p2] = [first, second]
while (p1 || p2) {
  if (p1 && p2) {
    if (p1.data <= p2.data) {
      // append p1 data to result
    } else {
      // append p2 data to result
    }
  } else if (p1) {
    // append p1 to result
  } else {
    // append p2 to result
  }
}

上面例子里 p1 和 p2 是指向兩個鏈表節點的指針，在循環中它們隨時可能變成空，因此要比較數據大小首先就要判斷兩個都不為空。而且注釋中的 append 代碼也會有一定重復。

為了解決這個問題，我們可以上個 kata 里調換指針的方法。完整代碼如下：

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

  while (p1 || p2) {
    // if either list is null, append the other one to the result list
    if (!p1 || !p2) {
      pr.next = (p1 || p2)
      break
    }

    if (p1.data <= p2.data) {
      pr = pr.next = new Node(p1.data)
      p1 = p1.next
    } else {
      // switch 2 lists to make sure it"s always p1 <= p2
      [p1, p2] = [p2, p1]
    }
  }

  return result.next
}

第 7 行判斷 p1 或 p2 為空，并且把非空的鏈表直接添加到 result 末尾，省去了繼續循環每個節點。第 17 行的指針調換讓 p1 始終小于等于 p2 ，從而避免了重復的 append 代碼。其他技巧如 dummy node 在之前的 kata 都有講，就不多說了。

參考資料

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

GPU云服務器云服務器用javascript操作xml 多鏈表c語言實現 java實現鏈表插入遍歷c語言實現鏈表

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

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

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

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

X_AirDu 2019-08-20 14:23 評論0 收藏0
用 JavaScript 實現鏈表操作 - 前言和目錄

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

BetaRabbit 2019-08-20 12:25 評論0 收藏0
LeetCode 之 JavaScript 解答第23題 —— 合并K個有序鏈表（Merge K S

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

zhou_you 2019-08-23 16:53 評論0 收藏0
LeetCode 之 JavaScript 解答第21題 —— 合并兩個有序鏈表（Merge Two

摘要：什么意思呢比如上方合并鏈表的代碼，分別明確函數的參數和返回值是什么參數是兩個合并的鏈表結點頭結點。返回值是合并后的鏈表。 Time：2019/4/9Title: Merge Two Sorted ListsDifficulty: EasyAuthor: 小鹿題目：Merge Two Sorted Lists Merge two sorted linked lists and re...

wdzgege 2019-08-23 16:51 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

摘要：微信公眾號記錄截圖記錄截圖目前關于這塊算法與數據結構的安排前。已攻略返回目錄目前已攻略篇文章。會根據題解以及留言內容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。本許可協議授權之外的使用權限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目錄不...

warmcheng 2019-08-26 10:09 評論0 收藏0