用 JavaScript 实现链表操作 - 13 Shuffle Merge

shiguibiao 发布于2019-08-20 14:21 / 826人阅读

摘要：需求实现函数把两个链表合并成一个。新链表的节点是交叉从两个链表中取的。通过行的调换指针，我们可以保证下一次循环就是对另一个链表进行操作了。这样一直遍历到两个链表末尾，返回结束。参考资料的代码实现的测试

TL;DR

把两个链表洗牌合并成一个，系列目录见前言和目录。

需求

实现函数 shuffleMerge() 把两个链表合并成一个。新链表的节点是交叉从两个链表中取的。这叫洗牌合并。举个例子，当传入的链表为 1 -> 2 -> 3 -> null 和 7 -> 13 -> 1 -> null 时，合并后的链表为 1 -> 7 -> 2 -> 13 -> 3 -> 1 -> null 。如果合并过程中一个链表的数据先取完了，就从另一个链表中取剩下的数据。这个函数应该返回一个新链表。

var first = 3 -> 2 -> 8 -> null
var second = 5 -> 6 -> 1 -> 9 -> 11 -> null
shuffleMerge(first, second) === 3 -> 5 -> 2 -> 6 -> 8 -> 1 -> 9 -> 11 -> null

如果参数之一为空，应该直接返回另一个链表（即使另一个链表也为空），不需要抛异常。

递归解法 1

代码如下：

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

  const list = new Node(first.data, new Node(second.data))
  list.next.next = shuffleMerge(first.next, second.next)
  return list
}

解题思路是，首先判断是否有一个链表为空，有就返回另一个，结束递归。这个判断过了，下面肯定是两个链表都不为空的情况。我们依次从两个链表中取第一个节点组合成新链表，然后递归 shuffleMerge 两个链表的后续节点，并把结果衔接到 list 后面。这段代码基本跟题目描述的意思一致。

递归解法 2

在上面的基础上我们还能做个更聪明的版本，代码如下：

function shuffleMergeV2(first, second) {
  if (!first || !second) return first || second
  return new Node(first.data, shuffleMerge(second, first.next))
}

通过简单的调换 first 和 second 的顺序，我们能把递归过程从 “先取 first 的首节点再取 second 的首节点” 变成 “总总是取 first 的首节点” 。解法 1 中的三行代码简化成了一行。

循环解法

循环其实才是本题的考点，因为这题主要是考指针（引用）操作。尤其是把 “依次移动两个链表的指针” 写进一个循环里。不过上个解法中调换两个链表顺序的方式也可以用到这里。代码如下：

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

  while (p1 || p2) {
    if (p1) {
      pr.next = new Node(p1.data)
      pr = pr.next
      p1 = p1.next
    }
    [p1, p2] = [p2, p1]
  }

  return result.next
}

首先我们生成一个 dummy node result ，同时建立一个 pr 代表 result 的尾节点（方便插入）。两个链表的指针分别叫 p1 和 p2 。在每次循环中我们都把 p1 的节点数据写到 result 链表的末尾，然后修改指针指向下一个节点。通过 12 行的调换指针，我们可以保证下一次循环就是对另一个链表进行操作了。这样一直遍历到两个链表末尾，返回 result.next 结束。

参考资料

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

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

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

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

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

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

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

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

BetaRabbit 2019-08-20 12:25 评论0 收藏0
用 JavaScript 实现链表操作 - 15 Merge Sort

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

X_AirDu 2019-08-20 14:23 评论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