资讯专栏INFORMATION COLUMN

用 JavaScript 实现链表操作 - 04 Insert Nth Node

894974231 / 1576人阅读

摘要:给定一个链表,一个范围在内的索引号,和一个数据,这个函数会生成一个新的节点并插入到指定的索引位置,并始终返回链表的头。的返回值一定是个链表,我们把它赋值给就行。但这个例子的边界情况是返回值不同如果,返回新节点。

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

相关文章

  • JavaScript 实现链表操作 - 前言和目录

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

    BetaRabbit 评论0 收藏0
  • JavaScript数据结构04 - 链表

    摘要:类表示要加入链表的项。循环链表和普通链表之间唯一的区别在于,最后一个元素指向下一个元素的指针不是引用,而是指向第一个元素。这里就不进行代码实现了,大家可以结合上面的单向链表和双向链表自己实现一个循环链表。 一、定义 1.1 概念 前面我们学习了数组这种数据结构。数组(或者也可以称为列表)是一种非常简单的存储数据序列的数据结构。在这一节,我们要学习如何实现和使用链表这种动态的数据结构,这...

    cheukyin 评论0 收藏0
  • JavaScript 实现链表操作 - 11 Alternating Split

    摘要:需求实现一个函数,把一个链表切分成两个。子链表的节点应该是在父链表中交替出现的。所以整个算法的解法就能很容易地用表示。唯一需要考虑的就是在每个循环体中判断节点该插入哪个链表。也有人使用持续增长的配合取余来做,比如。 TL;DR 把一个链表交替切分成两个,系列目录见 前言和目录 。 需求 实现一个 alternatingSplit() 函数,把一个链表切分成两个。子链表的节点应该是在父链...

    jsyzchen 评论0 收藏0
  • JavaScript 实现链表操作 - 03 Get Nth Node

    摘要:获得链表的第个节点。需求实现一个方法,传入一个链表和一个索引,返回索引代表的节点。递归版本假设函数定义为,递归过程为当为零,直接返回该节点,否则递归调用。如果循环结束还没有查到节点,那肯定是链表或者索引不合法,直接抛异常即可。 TL;DR 获得链表的第 N 个节点。系列目录见 前言和目录 。 需求 实现一个 getNth() 方法,传入一个链表和一个索引,返回索引代表的节点。索引以 0...

    syoya 评论0 收藏0
  • leetcode-019-删除链表倒数第N个结点(Remove Nth Node From End

    摘要:第题给定一个链表,删除链表的倒数第个节点,并且返回链表的头结点。因为,若有一个真正的头结点,则所有的元素处理方式都一样。但以第一个有效元素为头结点,就导致算法的不一致,需要单独处理第一个有效元素头结点。 leetcode第19题 Given a linked list, remove the n-th node from the end of list and return its h...

    brianway 评论0 收藏0

发表评论

0条评论

894974231

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<