用 JavaScript 实现链表操作 - 14 Sorted Merge

jzman 发布于2019-08-20 14:21 / 2381人阅读

摘要：需求实现函数把两个升序排列的链表合并成一个新链表，新链表也必须是升序排列的。有一些边界情况要考虑或可能为，在合并过程中或的数据有可能先取完。第行的指针调换让始终小于等于，从而避免了重复的代码。参考资料的代码实现的测试

TL;DR

把两个升序排列的链表合并成一个，系列目录见前言和目录。

需求

实现函数 sortedMerge() 把两个升序排列的链表合并成一个新链表，新链表也必须是升序排列的。这个函数应该对每个输入的链表都只遍历一次。

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

有一些边界情况要考虑：first 或 second 可能为 null ，在合并过程中 first 或 second 的数据有可能先取完。如果一个链表为空，就返回另一个链表（即使它也为空），不需要抛出异常。

在做这个 kata 之前，建议先完成 Shuffle Merge 。

递归解法

代码如下：

function sortedMerge(first, second) {
  if (!first || !second) return first || second

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

跟上个 kata 类似的思路。不过为了保证最后的结果是升序排列的，我们要取两个链表中值更小的首节点，添加到结果链表的末尾。思路就不赘述了。

循环解法

循环是这个 kata 有意思的一点，很多边界情况的判断也发生在这里。很容易写出这样的 if/else ：

let [p1, p2] = [first, second]
while (p1 || p2) {
  if (p1 && p2) {
    if (p1.data <= p2.data) {
      // append p1 data to result
    } else {
      // append p2 data to result
    }
  } else if (p1) {
    // append p1 to result
  } else {
    // append p2 to result
  }
}

上面例子里 p1 和 p2 是指向两个链表节点的指针，在循环中它们随时可能变成空，因此要比较数据大小首先就要判断两个都不为空。而且注释中的 append 代码也会有一定重复。

为了解决这个问题，我们可以上个 kata 里调换指针的方法。完整代码如下：

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

  while (p1 || p2) {
    // if either list is null, append the other one to the result list
    if (!p1 || !p2) {
      pr.next = (p1 || p2)
      break
    }

    if (p1.data <= p2.data) {
      pr = pr.next = new Node(p1.data)
      p1 = p1.next
    } else {
      // switch 2 lists to make sure it"s always p1 <= p2
      [p1, p2] = [p2, p1]
    }
  }

  return result.next
}

第 7 行判断 p1 或 p2 为空，并且把非空的链表直接添加到 result 末尾，省去了继续循环每个节点。第 17 行的指针调换让 p1 始终小于等于 p2 ，从而避免了重复的 append 代码。其他技巧如 dummy node 在之前的 kata 都有讲，就不多说了。

参考资料

Codewars Kata
GitHub 的代码实现
GitHub 的测试

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

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

转载请注明本文地址：https://www.ucloud.cn/yun/81566.html

用 JavaScript 实现链表操作 - 15 Merge Sort

摘要：需求实现函数进行归并排序。解法归并排序的运行方式是，递归的把一个大链表切分成两个小链表。切分到最后就全是单节点链表了，而单节点链表可以被认为是已经排好序的。这时候再两两合并，最终会得到一个完整的已排序链表。用把排好序的两个链表合并起来。 TL;DR 对链表进行归并排序，系列目录见前言和目录。需求实现函数 mergeSort() 进行归并排序。注意这种排序法需要使用递归。在 fr...

X_AirDu 2019-08-20 14:23 评论0 收藏0
用 JavaScript 实现链表操作 - 前言和目录

摘要：我打算写一个链表操作的系列，来自的系列，实现语言是。通过自己实现一个链表和常用操作，可以加深理解这类数据结构的优缺点。链表经常用来训练指针操作，虽然这只对适用，但等高级语言中控制引用的思路其实也差不多。 TL;DR 我打算写一个链表操作的系列，来自 Codewars 的 Linked List 系列 kata ，实现语言是 JavaScript 。这篇是开篇，简单描述了一下我写这个的目...

BetaRabbit 2019-08-20 12:25 评论0 收藏0
LeetCode 之 JavaScript 解答第23题 —— 合并K个有序链表（Merge K S

摘要：分治算法递归每层操作分解将原问题分解成一系列的子问题。分治算法满足的条件可分解原问题与分解成的小问题具有相同的模式无关联原问题分解成的子问题可以独立求解，子问题之间没有相关性，这一点是分治算法跟动态规划的明显区别。 Time：2019/4/10Title: Merge K Sorted ListsDifficulty: DifficultyAuthor: 小鹿题目：Merge K...

zhou_you 2019-08-23 16:53 评论0 收藏0
LeetCode 之 JavaScript 解答第21题 —— 合并两个有序链表（Merge Two

摘要：什么意思呢比如上方合并链表的代码，分别明确函数的参数和返回值是什么参数是两个合并的链表结点头结点。返回值是合并后的链表。 Time：2019/4/9Title: Merge Two Sorted ListsDifficulty: EasyAuthor: 小鹿题目：Merge Two Sorted Lists Merge two sorted linked lists and re...

wdzgege 2019-08-23 16:51 评论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