用 JavaScript 實現鏈表操作 - 05 Sorted Insert

junbaor 發布于2019-08-21 11:23 / 735人閱讀

摘要：把節點插入一個已排序的鏈表。這個函數接受兩個參數一個鏈表的頭節點和一個數據，并且始終返回新鏈表的頭節點。這是鏈表的一個常用技巧。另外合理使用可以簡化不少循環的代碼。

TL;DR

把節點插入一個已排序的鏈表。系列目錄見前言和目錄。

需求

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

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)

遞歸版本

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

當 head 為空，即空鏈表，直接返回新節點：

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

當 head 的值大于或等于 data 時，新節點也應該插入頭部：

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

如果以上兩點都不滿足，data 就應該插入后續的節點了，這種 “把數據插入某鏈表” 的邏輯恰好符合 sortedInsert 的定義，因為這個函數始終返回修改后的鏈表，我們可以新鏈表賦值給 head.next 完成鏈接：

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

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

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

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

循環版本

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

先上代碼：

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
  }
}

這段代碼比較復雜，主要有幾個邊界情況處理：

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

因為插入節點的操作需要連接前后兩個節點，循環體要維護 prevNode 和 node 兩個變量，這也間接導致 for 的寫法會比較麻煩，所以才用 while 。

循環版本 - dummy node

我們可以用上一個 kata 中提到的 dummy node 來解決鏈表循環中頭結點的 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
  }
}

這段代碼簡化了第一版循環中返回 head 還是 new Node(...) 的問題。但能不能繼續簡化一下每次循環中維護兩個節點變量的問題呢？

循環版本 - dummy node & check next node

為什么要在循環中維護兩個變量 prevNode 和 node ？這是因為新節點要插入兩個節點之間，而我們每次循環的當前節點是 node ，單鏈表中的節點沒辦法引用到上一個節點，所以才需要維護一個 prevNode 。

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

簡化后的代碼如下，順帶一提，因為可以少維護一個變量，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
    }
  }
}

總結

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

參考資料

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

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

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

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

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

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

BetaRabbit 2019-08-20 12:25 評論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
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經到題，所以后面會調整自己，在刷算法與數據結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚有什么區別...

tain335 2019-08-26 10:28 評論0 收藏0
用 JavaScript 實現鏈表操作 - 16 Sorted Intersect

摘要：需求實現函數取兩個已排序的鏈表的交集，交集指兩個鏈表都有的節點，節點不一定連續。每個鏈表應該只遍歷一次。結果鏈表中不能包含重復的節點。當我們對比和的值時，有這幾種情況，這時節點肯定交集，加入結果鏈表中。 TL;DR 一次遍歷取兩個排序鏈表的交集，系列目錄見前言和目錄。需求實現函數 sortedIntersect() 取兩個已排序的鏈表的交集，交集指兩個鏈表都有的節點，節點不一定...

zhigoo 2019-08-20 14:25 評論0 收藏0
用 JavaScript 實現鏈表操作 - 14 Sorted Merge

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

jzman 2019-08-20 14:21 評論0 收藏0