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

junbaor 發(fā)布于2019-08-21 11:23 / 748人閱讀

摘要：把節(jié)點(diǎn)插入一個(gè)已排序的鏈表。這個(gè)函數(shù)接受兩個(gè)參數(shù)一個(gè)鏈表的頭節(jié)點(diǎn)和一個(gè)數(shù)據(jù)，并且始終返回新鏈表的頭節(jié)點(diǎn)。這是鏈表的一個(gè)常用技巧。另外合理使用可以簡化不少循環(huán)的代碼。

TL;DR

把節(jié)點(diǎn)插入一個(gè)已排序的鏈表。系列目錄見前言和目錄。

需求

寫一個(gè) sortedInsert() 函數(shù)，把一個(gè)節(jié)點(diǎn)插入一個(gè)已排序的鏈表中，鏈表為升序排列。這個(gè)函數(shù)接受兩個(gè)參數(shù)：一個(gè)鏈表的頭節(jié)點(diǎn)和一個(gè)數(shù)據(jù)，并且始終返回新鏈表的頭節(jié)點(diǎn)。

sortedInsert(1 -> 2 -> 3 -> null, 4) === 1 -> 2 -> 3 -> 4 -> null)
sortedInsert(1 -> 7 -> 8 -> null, 5) === 1 -> 5 -> 7 -> 8 -> null)
sortedInsert(3 -> 5 -> 9 -> null, 7) === 3 -> 5 -> 7 -> 9 -> null)

遞歸版本

我們可以從簡單的情況推演遞歸的算法。下面假定函數(shù)簽名為 sortedInsert(head, data) 。

當(dāng) head 為空，即空鏈表，直接返回新節(jié)點(diǎn)：

if (!head) return new Node(data, null)

當(dāng) head 的值大于或等于 data 時(shí)，新節(jié)點(diǎn)也應(yīng)該插入頭部：

if (head.data >= data) return new Node(data, head)

如果以上兩點(diǎn)都不滿足，data 就應(yīng)該插入后續(xù)的節(jié)點(diǎn)了，這種 “把數(shù)據(jù)插入某鏈表” 的邏輯恰好符合 sortedInsert 的定義，因?yàn)檫@個(gè)函數(shù)始終返回修改后的鏈表，我們可以新鏈表賦值給 head.next 完成鏈接：

head.next = sortedInsert(head.next, data)
return head

整合起來代碼如下，非常簡單并且有表達(dá)力：

function sortedInsert(head, data) {
  if (!head || data <= head.data) return new Node(data, head)

  head.next = sortedInsert(head.next, data)
  return head
}

循環(huán)版本

循環(huán)邏輯是這樣：從頭到尾檢查每個(gè)節(jié)點(diǎn)，對第 n 個(gè)節(jié)點(diǎn)，如果數(shù)據(jù)小于或等于節(jié)點(diǎn)的值，則新建一個(gè)節(jié)點(diǎn)插入節(jié)點(diǎn) n 和節(jié)點(diǎn) n-1 之間。如果數(shù)據(jù)大于節(jié)點(diǎn)的值，則對下個(gè)節(jié)點(diǎn)做同樣的判斷，直到結(jié)束。

先上代碼：

function sortedInsertV2(head, data) {
  let node = head
  let prevNode

  while (true) {
    if (!node || data <= node.data) {
      let newNode = new Node(data, node)
      if (prevNode) {
        prevNode.next = newNode
        return head
      } else {
        return newNode
      }
    }

    prevNode = node
    node = node.next
  }
}

這段代碼比較復(fù)雜，主要有幾個(gè)邊界情況處理：

函數(shù)需要始終返回新鏈表的頭，但插入的節(jié)點(diǎn)可能在鏈表頭部或者其他地方，所以返回值需要判斷是返回新節(jié)點(diǎn)還是 head 。

因?yàn)椴迦牍?jié)點(diǎn)的操作需要連接前后兩個(gè)節(jié)點(diǎn)，循環(huán)體要維護(hù) prevNode 和 node 兩個(gè)變量，這也間接導(dǎo)致 for 的寫法會(huì)比較麻煩，所以才用 while 。

循環(huán)版本 - dummy node

我們可以用上一個(gè) kata 中提到的 dummy node 來解決鏈表循環(huán)中頭結(jié)點(diǎn)的 if/else 判斷，從而簡化一下代碼：

function sortedInsertV3(head, data) {
  const dummy = new Node(null, head)
  let prevNode = dummy
  let node = dummy.next

  while (true) {
    if (!node || node.data > data) {
      prevNode.next = new Node(data, node)
      return dummy.next
    }

    prevNode = node
    node = node.next
  }
}

這段代碼簡化了第一版循環(huán)中返回 head 還是 new Node(...) 的問題。但能不能繼續(xù)簡化一下每次循環(huán)中維護(hù)兩個(gè)節(jié)點(diǎn)變量的問題呢？

循環(huán)版本 - dummy node & check next node

為什么要在循環(huán)中維護(hù)兩個(gè)變量 prevNode 和 node ？這是因?yàn)樾鹿?jié)點(diǎn)要插入兩個(gè)節(jié)點(diǎn)之間，而我們每次循環(huán)的當(dāng)前節(jié)點(diǎn)是 node ，單鏈表中的節(jié)點(diǎn)沒辦法引用到上一個(gè)節(jié)點(diǎn)，所以才需要維護(hù)一個(gè) prevNode 。

如果在每次循環(huán)中檢查的主體是 node.next 呢？這個(gè)問題就解決了。換言之，我們檢查的是數(shù)據(jù)是否適合插入到 node 和 node.next 之間。這種做法的唯一問題是第一次循環(huán)，我們需要 node.next 指向頭結(jié)點(diǎn)，那 node 本身又是什么？ dummy node 正好解決了這個(gè)問題。這塊有點(diǎn)繞，不懂的話可以仔細(xì)想想。這是鏈表的一個(gè)常用技巧。

簡化后的代碼如下，順帶一提，因?yàn)榭梢陨倬S護(hù)一個(gè)變量，while 可以簡化成 for 了：

function sortedInsertV4(head, data) {
  const dummy = new Node(null, head)

  for (let node = dummy; node; node = node.next) {
    const nextNode = node.next
    if (!nextNode || nextNode.data >= data) {
      node.next = new Node(data, nextNode)
      return dummy.next
    }
  }
}

總結(jié)

這個(gè) kata 是遞歸簡單循環(huán)麻煩的一個(gè)例子，有比較才會(huì)理解遞歸的優(yōu)雅之處。另外合理使用 dummy node 可以簡化不少循環(huán)的代碼。算法相關(guān)的代碼和測試我都放在 GitHub 上，如果對你有幫助請幫我點(diǎn)個(gè)贊！

參考資料

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