用 JavaScript 实现链表操作 - 17 Iterative Reverse

only_do 发布于2019-08-20 14:33 / 2233人阅读

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

TL;DR

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

需求

实现方法 reverse() 用循环的方式反转链表，链表应该只遍历一次。注意这个函数直接修改了链表本身，所以不需要返回值。

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

解法

代码如下：

function reverse(list) {
  if (!list) return null

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

  list.data = result.data
  list.next = result.next
}

思路是，从前到后遍历链表，对每个节点复制一份，并让它的 next 指向前一个节点。最后 result 就是一个反转的新链表了。那么如何修改 list 呢？很简单，把 result 的首节点值赋给 list ，然后让 list 指向 result 的第二个节点就行。

参考资料

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

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

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

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

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

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

BetaRabbit 2019-08-20 12:25 评论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
用 JavaScript 实现链表操作 - 18 Recursive Reverse

摘要：需求实现函数用递归的方式反转链表。整理一番后的代码如下上面这段代码同时也是尾递归。在递归函数中开额外的参数很是常见的做法，也是尾递归优化的必要手段。 TL;DR 用递归的方式反转链表，系列目录见前言和目录。需求实现函数 reverse() 用递归的方式反转链表。例子如下： var list = 2 -> 1 -> 3 -> 6 -> 5 -> null reverse(list...

DesGemini 2019-08-20 14:35 评论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 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0