用 JavaScript 實現鏈表操作 - 16 Sorted Intersect

zhigoo 發布于2019-08-20 14:25 / 2237人閱讀

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

TL;DR

一次遍歷取兩個排序鏈表的交集，系列目錄見前言和目錄。

需求

實現函數 sortedIntersect() 取兩個已排序的鏈表的交集，交集指兩個鏈表都有的節點，節點不一定連續。每個鏈表應該只遍歷一次。結果鏈表中不能包含重復的節點。

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

分析

最容易想到的解法可能是從鏈表 A 中取一個節點，然后遍歷鏈表 B 找到相同的節點加入結果鏈表，最后取鏈表 A 的下一個節點重復該步驟。但這題有 每個鏈表只能遍歷一次 的限制，那么如何做呢？

我們先假象有兩個指針 p1 和 p2，分別指向兩個鏈表的首節點。當我們對比 p1 和 p2 的值時，有這幾種情況：

p1.data === p2.data ，這時節點肯定交集，加入結果鏈表中。因為兩個節點都用過了，我們可以同時后移 p1 和 p2 比較下一對節點。

p1.data < p2.data ，我們應該往后移動 p1 ，不動 p2 ，因為鏈表是升序排列的，p1 的后續節點有可能會跟 p2 一樣大。

p1.data > p2.data ，跟上面相反，移動 p2 。

p1 或 p2 為空，后面肯定沒有交集了，遍歷結束。

基本思路就是這樣，遞歸和循環都是如此。

遞歸解法

代碼如下：

function sortedIntersect(first, second) {
  if (!first || !second) return null

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

function nextDifferent(node) {
  let nextNode = node.next
  while (nextNode && nextNode.data === node.data) nextNode = nextNode.next
  return nextNode
}

需要注意的是不能加入重復節點的判斷。我是在第 5 行兩個鏈表的節點相等后，往后遍歷到下一個值不同的節點，為此多帶帶寫了個 nextDifferent 函數。這個做法比較符合我的思路，但其實也可以寫進循環體中，各位可以自行思考。

循環解法

代碼如下，不贅述了：

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

  while (p1 || p2) {
    if (!p1 || !p2) break

    if (p1.data === p2.data) {
      pr = pr.next = new Node(p1.data)
      p1 = nextDifferent(p1)
      p2 = nextDifferent(p2)
    } else if (p1.data < p2.data) {
      p1 = p1.next
    } else {
      p2 = p2.next
    }
  }

  return result.next
}

參考資料

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

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

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

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

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

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

BetaRabbit 2019-08-20 12:25 評論0 收藏0
用 JavaScript 實現鏈表操作 - 05 Sorted Insert

摘要：把節點插入一個已排序的鏈表。這個函數接受兩個參數一個鏈表的頭節點和一個數據，并且始終返回新鏈表的頭節點。這是鏈表的一個常用技巧。另外合理使用可以簡化不少循環的代碼。 TL;DR 把節點插入一個已排序的鏈表。系列目錄見前言和目錄。需求寫一個 sortedInsert() 函數，把一個節點插入一個已排序的鏈表中，鏈表為升序排列。這個函數接受兩個參數：一個鏈表的頭節點和一個數據，并且...

junbaor 2019-08-21 11:23 評論0 收藏0
用 JavaScript 實現鏈表操作 - 14 Sorted Merge

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

jzman 2019-08-20 14:21 評論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