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

894974231 发布于2019-08-22 10:50 / 1599人阅读

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

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 的测试

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

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

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

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

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

BetaRabbit 2019-08-20 12:25 评论0 收藏0
JavaScript数据结构04 - 链表

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

cheukyin 2019-08-23 10:39 评论0 收藏0
用 JavaScript 实现链表操作 - 11 Alternating Split

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

jsyzchen 2019-08-20 14:02 评论0 收藏0
用 JavaScript 实现链表操作 - 03 Get Nth Node

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

syoya 2019-08-21 14:53 评论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 2019-08-23 14:34 评论0 收藏0