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

資訊專欄INFORMATION COLUMN

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

jzman / 2388人閱讀

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

TL;DR

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

需求

實(shí)現(xiàn)函數(shù) sortedMerge() 把兩個(gè)升序排列的鏈表合并成一個(gè)新鏈表，新鏈表也必須是升序排列的。這個(gè)函數(shù)應(yīng)該對(duì)每個(gè)輸入的鏈表都只遍歷一次。

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 的數(shù)據(jù)有可能先取完。如果一個(gè)鏈表為空，就返回另一個(gè)鏈表（即使它也為空），不需要拋出異常。

在做這個(gè) 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))
  }
}

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

循環(huán)解法

循環(huán)是這個(gè) kata 有意思的一點(diǎn)，很多邊界情況的判斷也發(fā)生在這里。很容易寫出這樣的 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 是指向兩個(gè)鏈表節(jié)點(diǎn)的指針，在循環(huán)中它們隨時(shí)可能變成空，因此要比較數(shù)據(jù)大小首先就要判斷兩個(gè)都不為空。而且注釋中的 append 代碼也會(huì)有一定重復(fù)。

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

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 末尾，省去了繼續(xù)循環(huán)每個(gè)節(jié)點(diǎn)。第 17 行的指針調(diào)換讓 p1 始終小于等于 p2 ，從而避免了重復(fù)的 append 代碼 。其他技巧如 dummy node 在之前的 kata 都有講，就不多說了。

參考資料

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

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

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

相關(guān)文章

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

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

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

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

    BetaRabbit 評(píng)論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 評(píng)論0 收藏0

  • LeetCode 之 JavaScript 解答第21題 —— 合并兩個(gè)有序鏈表（Merge Two

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

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

  • LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

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

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

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

0條評(píng)論

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