摘要:需求实现一个函数,把源链表的头结点移到目标链表的开头。要求是不能修改两个链表的引用。跟前一个不同的是,这个是在不改变引用的情况下修改两个链表自身。最优的方案这个算法考的是对链表节点的插入和删除。大致思路为对做删除一个节点的操作。
TL;DR
用 in-place 的方式把一个链表的首节点移到另一个链表(不改变链表的引用),系列目录见 前言和目录 。
需求实现一个 moveNode() 函数,把源链表的头结点移到目标链表的开头。要求是不能修改两个链表的引用。
var source = 1 -> 2 -> 3 -> null var dest = 4 -> 5 -> 6 -> null moveNode(source, dest) source === 2 -> 3 -> null dest === 1 -> 4 -> 5 -> 6 -> null
当碰到以下的情况应该抛出异常:
源链表为 null
目标链表为 null
源链表是空节点,data 属性为 null 的节点定义为空节点。
跟 前一个 kata 不同的是,这个 kata 是在不改变引用的情况下修改两个链表自身。因此 moveNode() 函数不需要返回值。同时这个 kata 也提出了 空节点 的概念。空节点会用于目标链表为空的情况(为了保持引用),在函数执行之后,目标链表会由空节点变成一个包含一个节点的链表。
你可以使用 第一个 kata 的 push 方法。
最优的方案这个算法考的是对链表节点的插入和删除。基本只对 source 和 dest 分别做一次操作,所以不用区分递归和循环。大致思路为:
对 source 做删除一个节点的操作。如果只有一个节点就直接置空。如果有多个节点,就把第二个节点的值赋给头节点,然后让头结点指向第三个节点。
对 dest 做插入一个节点的操作。如果头结点为空就直接赋值,否则把头结点复制一份,作为第二个节点插入到链表中,再把新值赋给头结点。
代码如下:
function moveNode(source, dest) { if (!source || !dest || source.data === null) throw new Error("invalid arguments") const data = source.data if (source.next) { source.data = source.next.data source.next = source.next.next } else { source.data = null } if (dest.data === null) { dest.data = data } else { dest.next = new Node(dest.data, dest.next) dest.data = data } }递归方案
这是我最开始思考的方案,差别在于对 dest 如何插入新节点的处理上用了递归。思路是把所有节点的 data 往后移一位,即把新值赋给第一个节点,第一个节点的值赋给第二个节点,第二个节点的值赋给第三个节点,以此类推。但实际操作中的顺序必须是反的,就是把倒数第二个节点的值赋给最后一个节点,倒数第三个节点的值赋给倒数第二个节点…… 这个思路对 dest 操作了 N 次,不如上一个解法的 1 次操作高效。不过也算是个有意思的递归用例,所以我仍然把它放了上来。
代码如下,主要看 pushInPlaceV2 :
function moveNodeV2(source, dest) { if (source === null || dest === null || source.isEmpty()) { throw new Error("invalid arguments") } pushInPlaceV2(dest, source.data) if (source.next) { source.data = source.next.data source.next = source.next.next } else { source.data = null } } function pushInPlaceV2(head, data) { if (!head) return new Node(data) if (!head.isEmpty()) head.next = pushInPlaceV2(head.next, head.data) head.data = data return head }总结
总是使用递归会产生惯性,导致忽略了数据结构的基本特性。链表的特性就是插入和删除的便利,改改引用就成了。
算法相关的代码和测试我都放在 GitHub 上,如果对你有帮助请帮我点个赞!
参考资料Codewars Kata
GitHub 的代码实现
GitHub 的测试
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/81149.html
摘要:我打算写一个链表操作的系列,来自的系列,实现语言是。通过自己实现一个链表和常用操作,可以加深理解这类数据结构的优缺点。链表经常用来训练指针操作,虽然这只对适用,但等高级语言中控制引用的思路其实也差不多。 TL;DR 我打算写一个链表操作的系列,来自 Codewars 的 Linked List 系列 kata ,实现语言是 JavaScript 。这篇是开篇,简单描述了一下我写这个的目...
摘要:需求实现一个函数,把源链表的头节点移到目标链表。当源链表为空时函数应抛出异常。为了简化起见,我们会用一个对象来存储改变后的源链表和目标链表的引用。它也是函数的返回值。解法配合,这个非常简单,注意这个函数没有改变两个链表本身。 TL;DR 把一个链表的首节点移到另一个链表。系列目录见 前言和目录 。 需求 实现一个 moveNode() 函数,把源链表的头节点移到目标链表。当源链表为空时...
摘要:相反,双向链表具有指向其前后元素的节点。另外,可以对链表进行排序。这个实用程序方法用于打印链表中的节点,仅用于调试目的。第行将更新为,这是从链表中弹出最后一个元素的行为。如果链表为空,则返回。 showImg(https://segmentfault.com/img/bVbsaI7?w=1600&h=228); 什么是链表 单链表是表示一系列节点的数据结构,其中每个节点指向链表中的下一...
摘要:插入排序维基百科一般来说,插入排序都采用在数组上实现。在放这个数之前,这个数的目标位置和原始位置之间的数都要先进行后移。最后,当,即遍历完整个原链表之后,新链表排序完成。 Problem Sort a linked list using insertion sort. Example Given 1->3->2->0->null, return 0->1->2->3->null. No...
摘要:栈被称为一种后入先出的数据结构。散列使用的数据结构叫做散列表。这些操作需要求助于其他数据结构,比如下面介绍的二叉查找树。 前言 在过去的几年中,得益于Node.js的兴起,JavaScript越来越广泛地用于服务器端编程。鉴于JavaScript语言已经走出了浏览器,程序员发现他们需要更多传统语言(比如C++和Java)提供的工具。这些工具包括传统的数据结构(如链表,栈,队列,图等),...
阅读 3379·2021-11-24 10:30
阅读 3238·2021-11-22 15:29
阅读 3692·2021-10-28 09:32
阅读 1174·2021-09-07 10:22
阅读 3320·2019-08-30 15:55
阅读 3602·2019-08-30 15:54
阅读 3476·2019-08-30 15:54
阅读 2817·2019-08-30 15:44