摘要:需求实现一个函数,把一个链表切分成两个。子链表的节点应该是在父链表中交替出现的。所以整个算法的解法就能很容易地用表示。唯一需要考虑的就是在每个循环体中判断节点该插入哪个链表。也有人使用持续增长的配合取余来做,比如。
TL;DR
把一个链表交替切分成两个,系列目录见 前言和目录 。
需求实现一个 alternatingSplit() 函数,把一个链表切分成两个。子链表的节点应该是在父链表中交替出现的。如果原链表是 a -> b -> a -> b -> a -> null ,则两个子链表分别为 a -> a -> a -> null 和 b -> b -> null 。
var list = 1 -> 2 -> 3 -> 4 -> 5 -> null alternatingSplit(list).first === 1 -> 3 -> 5 -> null alternatingSplit(list).second === 2 -> 4 -> null
为了简化结果,函数会返回一个 Context 对象来保存两个子链表,Context 结构如下所示:
function Context(first, second) { this.first = first this.second = second }
如果原链表为 null 或者只有一个节点,应该抛出异常。
递归版本代码如下:
function alternatingSplit(head) { if (!head || !head.next) throw new Error("invalid arguments") return new Context(split(head), split(head.next)) } function split(head) { const list = new Node(head.data) if (head.next && head.next.next) list.next = split(head.next.next) return list }
这个解法的核心思路在于 split ,这个方法接收一个链表并返回一个以奇数位的节点组成的子链表。所以整个算法的解法就能很容易地用 new Context(split(head), split(head.next)) 表示。
另一个递归版本代码如下:
function alternatingSplitV2(head) { if (!head || !head.next) throw new Error("invalid arguments") return new Context(...splitV2(head)) } function splitV2(head) { if (!head) return [null, null] const first = new Node(head.data) const [second, firstNext] = splitV2(head.next) first.next = firstNext return [first, second] }
这里的 splitV2 的作用跟整个算法的含义一样 -- 接收一个链表并返回交叉分割的两个子链表(以数组表示)。第一个子链表的头自然是 new Node(head.data) ,第二个子链表呢?它其实是 splitV2(head.next) 的第一个子链表(见第 4 行)。理解这个逻辑后就能明白递归过程。
循环版本代码如下:
function alternatingSplitV3(head) { if (!head || !head.next) throw new Error("invalid arguments") const first = new Node() const second = new Node() const tails = [first, second] for (let node = head, idx = 0; node; node = node.next, idx = idx ? 0 : 1) { tails[idx].next = new Node(node.data) tails[idx] = tails[idx].next } return new Context(first.next, second.next) }
这个思路是,先用两个变量代表子链表,然后对整个链表进行一次遍历,分别把节点交替插入每个子链表中。唯一需要考虑的就是在每个循环体中判断节点该插入哪个链表。我用的是 idx 变量,在每轮循环中把它交替设置成 0 和 1 。也有人使用持续增长的 idx 配合取余来做,比如 idx % 2 。做法有很多种,就不赘述了。
这里也用了 dummy node 的技巧来简化 “判断首节点是否为空” 的情况。关于这个技巧可以看看 Insert Nth Node
参考资料Codewars Kata
GitHub 的代码实现
GitHub 的测试
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/81377.html
摘要:我打算写一个链表操作的系列,来自的系列,实现语言是。通过自己实现一个链表和常用操作,可以加深理解这类数据结构的优缺点。链表经常用来训练指针操作,虽然这只对适用,但等高级语言中控制引用的思路其实也差不多。 TL;DR 我打算写一个链表操作的系列,来自 Codewars 的 Linked List 系列 kata ,实现语言是 JavaScript 。这篇是开篇,简单描述了一下我写这个的目...
摘要:需求实现函数把链表居中切分成两个子链表一个前半部分,另一个后半部分。提示一个简单的做法是计算链表的长度,然后除以得出前半部分的长度,最后分割链表。最后用把数组转回链表。参考资料的代码实现的测试 TL;DR 把一个链表居中切分成两个,系列目录见 前言和目录 。 需求 实现函数 frontBackSplit() 把链表居中切分成两个子链表 -- 一个前半部分,另一个后半部分。如果节点数为奇...
摘要:需求实现函数进行归并排序。解法归并排序的运行方式是,递归的把一个大链表切分成两个小链表。切分到最后就全是单节点链表了,而单节点链表可以被认为是已经排好序的。这时候再两两合并,最终会得到一个完整的已排序链表。用把排好序的两个链表合并起来。 TL;DR 对链表进行归并排序,系列目录见 前言和目录 。 需求 实现函数 mergeSort() 进行归并排序。注意这种排序法需要使用递归。在 fr...
摘要:需求实现函数把两个链表合并成一个。新链表的节点是交叉从两个链表中取的。通过行的调换指针,我们可以保证下一次循环就是对另一个链表进行操作了。这样一直遍历到两个链表末尾,返回结束。参考资料的代码实现的测试 TL;DR 把两个链表洗牌合并成一个,系列目录见 前言和目录 。 需求 实现函数 shuffleMerge() 把两个链表合并成一个。新链表的节点是交叉从两个链表中取的。这叫洗牌合并。举...
阅读 2726·2023-04-26 01:47
阅读 3569·2023-04-25 23:45
阅读 2335·2021-10-13 09:39
阅读 573·2021-10-09 09:44
阅读 1748·2021-09-22 15:59
阅读 2661·2021-09-13 10:33
阅读 1614·2021-09-03 10:30
阅读 613·2019-08-30 15:53