摘要:给定一个链表,一个范围在内的索引号,和一个数据,这个函数会生成一个新的节点并插入到指定的索引位置,并始终返回链表的头。的返回值一定是个链表,我们把它赋值给就行。但这个例子的边界情况是返回值不同如果,返回新节点。
TL;DR
插入第 N 个节点。系列目录见 前言和目录 。
需求实现一个 insertNth() 方法,在链表的第 N 个索引处插入一个新节点。
insertNth() 可以看成是 01 Push & Build List 中的 push() 函数的更通用版本。给定一个链表,一个范围在 0..length 内的索引号,和一个数据,这个函数会生成一个新的节点并插入到指定的索引位置,并始终返回链表的头。
insertNth(1 -> 2 -> 3 -> null, 0, 7) === 7 -> 1 -> 2 -> 3 -> null) insertNth(1 -> 2 -> 3 -> null, 1, 7) === 1 -> 7 -> 2 -> 3 -> null) insertNth(1 -> 2 -> 3 -> null, 3, 7) === 1 -> 2 -> 3 -> 7 -> null)
如果索引号超出了链表的长度,函数应该抛出异常。
实现这个函数允许使用第一个 kata 中的 push 方法。
递归版本让我们先回忆一下 push 函数的用处,指定一个链表的头和一个数据,push 会生成一个新节点并添加到链表的头部,并返回新链表的头。比如:
push(null, 23) === 23 -> null push(1 -> 2 -> null, 23) === 23 -> 1 -> 2 -> null
现在看看 insertNth ,假设函数方法签名是 insertNth(head, index, data) ,那么有两种情况:
如果 index === 0 ,则等同于调用 push 。实现为 push(head, data) 。
如果 index !== 0 ,我们可以把下一个节点当成子链表传入 insertNth ,并让 index 减一。insertNth 的返回值一定是个链表,我们把它赋值给 head.next 就行。这就是一个递归过程。如果这次递归的 insertNth 完不成任务,它会继续递归到下一个节点,直到 index === 0 的最简单情况,或 head 为空抛出异常(索引过大)。
完整代码实现为:
function insertNth(head, index, data) { if (index === 0) return push(head, data) if (!head) throw "invalid argument" head.next = insertNth(head.next, index - 1, data) return head }循环版本
如果能理解递归版本的 head.next = insertNth(...) ,那么循环版本也不难实现。不同的是,在循环中我们遍历到 index 的前一个节点,然后用 push 方法生成新节点,并赋值给前一个节点的 next 属性形成一个完整的链表。
完整代码实现如下:
function insertNthV2(head, index, data) { if (index === 0) return push(head, data) for (let node = head, idx = 0; node; node = node.next, idx++) { if (idx + 1 === index) { node.next = push(node.next, data) return head } } throw "invalid argument" }
这里有一个边界情况要注意。因为 insertNth 要求返回新链表的头。根据 index 是否为 0 ,这个新链表的头可能是生成的新节点,也可能就是老链表的头 。这点如果写进 for 循环就不可避免有 if/else 的返回值判断。所以我们把 index === 0 的情况多带带拿出来放在函数顶部。这个边界情况并非无法纳入循环中,我们下面介绍的一个技巧就与此有关。
循环版本 - dummy node在之前的几个 kata 里,我们提到循环可以更好的容纳边界情况,因为一些条件判断都能写到 for 的头部中去。但这个例子的边界情况是返回值不同:
如果 index === 0 ,返回新节点 。
如果 index !== 0 ,返回 head 。新节点会被插入 head 之后的某个节点链条中。
如何解决这个问题呢,我们可以在 head 前面再加入一个节点(数据任意,一般赋值 null)。这个节点称为 dummy 节点。这样一来,不管新节点插入到哪里,dummy.next 都可以引用到修改后的链表。
代码实现如下,注意 return 的不同。
function insertNthV3(head, index, data) { const dummy = push(head, null) for (let node = dummy, idx = 0; node; node = node.next, idx++) { if (idx === index) { node.next = push(node.next, data) return dummy.next } } throw "invalid argument" }
dummy 节点是很多链表操作的常用技巧,虽然在这个 kata 中使用 dummy 节点的代码量并没有变少,但这个技巧在后续的一些复杂 kata 中会非常有用。
参考资料Codewars Kata
GitHub 的代码实现
GitHub 的测试
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/91358.html
摘要:我打算写一个链表操作的系列,来自的系列,实现语言是。通过自己实现一个链表和常用操作,可以加深理解这类数据结构的优缺点。链表经常用来训练指针操作,虽然这只对适用,但等高级语言中控制引用的思路其实也差不多。 TL;DR 我打算写一个链表操作的系列,来自 Codewars 的 Linked List 系列 kata ,实现语言是 JavaScript 。这篇是开篇,简单描述了一下我写这个的目...
摘要:类表示要加入链表的项。循环链表和普通链表之间唯一的区别在于,最后一个元素指向下一个元素的指针不是引用,而是指向第一个元素。这里就不进行代码实现了,大家可以结合上面的单向链表和双向链表自己实现一个循环链表。 一、定义 1.1 概念 前面我们学习了数组这种数据结构。数组(或者也可以称为列表)是一种非常简单的存储数据序列的数据结构。在这一节,我们要学习如何实现和使用链表这种动态的数据结构,这...
摘要:需求实现一个函数,把一个链表切分成两个。子链表的节点应该是在父链表中交替出现的。所以整个算法的解法就能很容易地用表示。唯一需要考虑的就是在每个循环体中判断节点该插入哪个链表。也有人使用持续增长的配合取余来做,比如。 TL;DR 把一个链表交替切分成两个,系列目录见 前言和目录 。 需求 实现一个 alternatingSplit() 函数,把一个链表切分成两个。子链表的节点应该是在父链...
摘要:获得链表的第个节点。需求实现一个方法,传入一个链表和一个索引,返回索引代表的节点。递归版本假设函数定义为,递归过程为当为零,直接返回该节点,否则递归调用。如果循环结束还没有查到节点,那肯定是链表或者索引不合法,直接抛异常即可。 TL;DR 获得链表的第 N 个节点。系列目录见 前言和目录 。 需求 实现一个 getNth() 方法,传入一个链表和一个索引,返回索引代表的节点。索引以 0...
摘要:第题给定一个链表,删除链表的倒数第个节点,并且返回链表的头结点。因为,若有一个真正的头结点,则所有的元素处理方式都一样。但以第一个有效元素为头结点,就导致算法的不一致,需要单独处理第一个有效元素头结点。 leetcode第19题 Given a linked list, remove the n-th node from the end of list and return its h...
阅读 988·2022-07-19 10:19
阅读 1758·2021-09-02 15:15
阅读 983·2019-08-30 15:53
阅读 2622·2019-08-30 13:45
阅读 2611·2019-08-26 13:57
阅读 1948·2019-08-26 12:13
阅读 971·2019-08-26 10:55
阅读 513·2019-08-26 10:46