用 JavaScript 实现链表操作 - 18 Recursive Reverse

DesGemini 发布于2019-08-20 14:35 / 1521人阅读

摘要：需求实现函数用递归的方式反转链表。整理一番后的代码如下上面这段代码同时也是尾递归。在递归函数中开额外的参数很是常见的做法，也是尾递归优化的必要手段。

TL;DR

用递归的方式反转链表，系列目录见前言和目录。

需求

实现函数 reverse() 用递归的方式反转链表。例子如下：

var list = 2 -> 1 -> 3 -> 6 -> 5 -> null
reverse(list) === 5 -> 6 -> 3 -> 1 -> 2 -> null

解法

让我们先思考一下递归的大概解法：

function reverse(head) {
  const node = new Node(head.data)
  const rest = reverse(head.next)
  // 把 node 放到 rest 的末尾，并返回 rest
}

麻烦的地方就在最后，把节点加入链表的末尾需要首先遍历整个链表，这无疑非常低效。我们在上一个 kata 的循环里是怎么解决的呢？维护一个 result 变量代表反转链表，然后每次把新节点放到 result 的头部，同时把新节点当做新的 result ，大概这个样子：

let result
for (let node = list; node; node = node.next) {
  result = new Node(node.data, result)
}

为了在递归里达到同样的效果，我们也必须维护这么一个变量。为了在每次递归过程中都能用到这个变量，我们得把它当函数的参数传递下去，reverse 的函数签名就变成这样：

function reverse(head, acc) { ... }

这里 acc 就是反转的链表。整理一番后的代码如下：

function reverse(head, acc = null) {
  return head ? reverse(head.next, new Node(head.data, acc)) : acc
}

上面这段代码同时也是尾递归。在递归函数中开额外的参数很是常见的做法，也是尾递归优化的必要手段。

参考资料

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

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

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

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

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

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

BetaRabbit 2019-08-20 12:25 评论0 收藏0
[Leetcode] Reverse Linked List 链表反转（递归与非递归）

摘要：代码描述调转指针解法非递归用三个指针，紧紧相邻，不断前进，每次将指向，将指向指向。描述递归解法测试结果 Reverse a singly linked list. 代码ReverseLinkedList.java package list; public class ReverseLinkedList { /** * 描述 Reverse a singly...

RyanHoo 2019-08-15 14:03 评论0 收藏0
用 JavaScript 实现链表操作 - 17 Iterative Reverse

摘要：需求实现方法用循环的方式反转链表，链表应该只遍历一次。注意这个函数直接修改了链表本身，所以不需要返回值。解法代码如下思路是，从前到后遍历链表，对每个节点复制一份，并让它的指向前一个节点。参考资料的代码实现的测试 TL;DR 用循环的方式反转链表，系列目录见前言和目录。需求实现方法 reverse() 用循环的方式反转链表，链表应该只遍历一次。注意这个函数直接修改了链表本身，所以...

only_do 2019-08-20 14:33 评论0 收藏0
LeetCode 之 JavaScript 解答第206题 —— 反转链表（Reverse Link

摘要：算法思路两种方法一般反转递归法一般解决定义三个指针，分别为，存储当前结点，指向反转好的结点的头结点，存储下一结点信息。递归法重点分析先确定终止条件当下一结点为时，返回当前节点判断当前的链表是否为递归找到尾结点，将其存储为头结点。 Time：2019/4/23Title: Reverse Linked ListDifficulty: EasyAuthor: 小鹿题目：Reverse...

zhangfaliang 2019-08-23 17:12 评论0 收藏0
[Leetcode] Add Two Numbers 链表数相加

摘要：过程同样是对齐相加，不足位补。迭代终止条件是两个都为。如果这是一个类的话该如何实现将链表或者数组作为成员变量，提供对其操作的各种方法。 Add Two Numbers You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order a...

Fourierr 2019-08-14 12:18 评论0 收藏0