用 JavaScript 实现链表操作 - 16 Sorted Intersect

zhigoo 发布于2019-08-20 14:25 / 2145人阅读

摘要：需求实现函数取两个已排序的链表的交集，交集指两个链表都有的节点，节点不一定连续。每个链表应该只遍历一次。结果链表中不能包含重复的节点。当我们对比和的值时，有这几种情况，这时节点肯定交集，加入结果链表中。

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 的测试

云服务器海外云主机用javascript操作xml 多链表c语言实现 java实现链表插入遍历c语言实现链表

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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