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

資訊專欄INFORMATION COLUMN

用 JavaScript 實現(xiàn)鏈表操作 - 16 Sorted Intersect

zhigoo / 2244人閱讀

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

TL;DR

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

需求

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

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 中取一個節(jié)點，然后遍歷鏈表 B 找到相同的節(jié)點加入結(jié)果鏈表，最后取鏈表 A 的下一個節(jié)點重復該步驟。但這題有 每個鏈表只能遍歷一次 的限制，那么如何做呢？

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

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

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

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

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

基本思路就是這樣，遞歸和循環(huán)都是如此。

遞歸解法

代碼如下：

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
}

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

循環(huán)解法

代碼如下，不贅述了：

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 的代碼實現(xiàn)
GitHub 的測試

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

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

相關(guān)文章

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

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

    BetaRabbit 評論0 收藏0

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

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

    junbaor 評論0 收藏0

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

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

    jzman 評論0 收藏0

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

    摘要：微信公眾號記錄截圖記錄截圖目前關(guān)于這塊算法與數(shù)據(jù)結(jié)構(gòu)的安排前。已攻略返回目錄目前已攻略篇文章。會根據(jù)題解以及留言內(nèi)容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。本許可協(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 評論0 收藏0

  • LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

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

    tain335 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<