用 JavaScript 实现链表操作 - 03 Get Nth Node

syoya 发布于2019-08-21 14:53 / 1598人阅读

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

TL;DR

获得链表的第 N 个节点。系列目录见前言和目录。

需求

实现一个 getNth() 方法，传入一个链表和一个索引，返回索引代表的节点。索引以 0 为起始，第一个元素索引为 0 ，第二个为 1 ，以此类推。比如：

getNth(1 -> 2 -> 3 -> null, 0).data === 1
getNth(1 -> 2 -> 3 -> null, 1).data === 2

传入的索引必须是在效范围内，即 0..length-1 ，如果索引不合法或者链表为空都需要抛出异常。

递归版本

假设函数定义为 getNth(head, idx) ，递归过程为：当 idx 为零，直接返回该节点，否则递归调用 getNth(head.next, idx - 1) 。再处理下边界情况就完成了，代码如下：

function getNth(head, idx) {
  if (!head || idx < 0) throw "invalid argument"
  if (idx === 0) return head
  return getNth(head.next, idx - 1)
}

循环版本

我选择的 for 循环，这样方便把边界情况检查都放到循环里去。如果循环结束还没有查到节点，那肯定是链表或者索引不合法，直接抛异常即可。对比这两个版本和 02 Length & Count 的例子，不难看出循环可以比递归更容易地处理边界情况，因为一些条件检查可以写进循环的头部，递归就得自己写 if/else 逻辑。

function getNthV2(head, idx) {
  for (let node = head; node && idx >= 0; node = node.next, idx--) {
    if (idx === 0) return node
  }
  throw "invalid argument"
}

参考资料

Codewars Kata
GitHub 的代码实现
GitHub 的测试

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

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

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

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

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

BetaRabbit 2019-08-20 12:25 评论0 收藏0
用 JavaScript 实现链表操作 - 04 Insert Nth Node

摘要：给定一个链表，一个范围在内的索引号，和一个数据，这个函数会生成一个新的节点并插入到指定的索引位置，并始终返回链表的头。的返回值一定是个链表，我们把它赋值给就行。但这个例子的边界情况是返回值不同如果，返回新节点。 TL;DR 插入第 N 个节点。系列目录见前言和目录。需求实现一个 insertNth() 方法，在链表的第 N 个索引处插入一个新节点。 insertNth() 可以...

894974231 2019-08-22 10:50 评论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
用 JavaScript 实现链表操作 - 11 Alternating Split

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

jsyzchen 2019-08-20 14:02 评论0 收藏0
leetcode19 Remove Nth Node From End of List 从链表中移除

摘要：虽然时间复杂度还是但是显然我们可以再一次遍历中完成这个任务。现在跳出下标的思路，从另一个角度分析。快慢节点之间的距离始终是。当快节点到达终点时，此时的慢节点就是所要删去的节点。题目要求 Given a linked list, remove the nth node from the end of list and return its head. For example, ...

YPHP 2019-08-14 18:05 评论0 收藏0