LeetCode 之 JavaScript 解答第206题 —— 反转链表（Reverse Link

zhangfaliang 发布于2019-08-23 17:12 / 3430人阅读

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

Time：2019/4/23
Title: Reverse Linked List
Difficulty: Easy
Author: 小鹿

题目：Reverse Linked List（反转链表）

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

Solve:

▉ 问题分析

1）反转链表的我们第一能够想到的方法就是最常用的方法，声明三个指针，把头结点变为尾结点，然后下一结点拼接到尾结点的头部，一次类推。说白了就是就是直接将链表指针反转就可以实现反转链表。

▉ 算法思路

两种方法：

一般反转

递归法

一般解决：

1）定义三个指针，分别为 Pnext、pre、current，current 存储当前结点， pre 指向反转好的结点的头结点，Pnext 存储下一结点信息。

2）判断当前结点是否可以反转（是否为空链表或链表大于 1 个结点）?

步骤：

1）Pnext 指针存储下一结点。

2）当前结点的 next 结点是否为 null (为 null 的话当前结点就是最后的一个结点)，如果为 null，将当前节点赋值为 head 头指针（断裂处）。

3）将 pre 指针指向的结点赋值当前节点 current 的下一结点 next。

4）然后让 pre 指针指向当前节点 current。

5）current 继续遍历, 当前节点指向 current 指向 Pnext。

递归法（重点分析）：

1）先确定终止条件：当下一结点为 null 时，返回当前节点；

2）判断当前的链表是否为 null；

3）递归找到尾结点，将其存储为头结点。

4）此时递归的层次是第二层递归，所以要设置为头结点的下一结点就是当前第二层结点，并且将第二节点的下一结点设置为 bull。

▉ 测试用例

1）链表是空链表。

2）当前链表的长度小于等于 1。

3）输入长度大于 1 的链表。

▉ 递归法

const reverseList = (head)=>{
       if(head == null || head.next == null){
           return head;
       }else{
           let newhead = reverseList(head.next);
           head.next.next = head;
           head.next = null;
           return newhead;
       }
   }

▉ 性能分析

时间复杂度：O(n)。只需遍历整个链表就可以完成反转，时间复杂度为 O(n)。
空间复杂度：O(1)。只需要常量级的空间，空间复杂度为 O(1)。

欢迎一起加入到 LeetCode 开源 Github 仓库，可以向 me 提交您其他语言的代码。在仓库上坚持和小伙伴们一起打卡，共同完善我们的开源小仓库！
Github：https://github.com/luxiangqia...
欢迎关注我个人公众号：「一个不甘平凡的码农」，记录了自己一路自学编程的故事。

服务器托管专线服务 python反转链表 javascript算法题汇编语言程序设计第二版课后题答案 javascript必问面试题

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

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

LeetCode 之 JavaScript 解答第344题 —— 反转字符串（Reverse Str

摘要：小鹿题目反转字符串编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组的形式给出。如果为奇数，当两个指针相等时，反转完毕。测试用例空字符串。奇数个数的字符串。长度为的字符串。考查内容对字符串的基本操作。 Time：2019/4/18Title: Reverse StringDifficulty: EasyAuthor: 小鹿题目：Reverse String(反转字...

bbbbbb 2019-08-23 17:03 评论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
LeetCode 之 JavaScript 解答第151题 —— 反转字符串中的单词

摘要：小鹿题目翻转字符串里的单词给定一个字符串，逐个翻转字符串中的每个单词。说明无空格字符构成一个单词。遇到空格之后，将单词进行倒序拼接。消除尾部的空格。测试用例空字符串。中间空格大于的字符串。 Time：2019/4/20Title: Reverse Words In a StringDifficulty: MidumnAuthor: 小鹿题目：Reverse Words In a ...

betacat 2019-08-23 17:05 评论0 收藏0
JS算法题之leetcode(1~10)

摘要：先去空白，去掉空白之后取第一个字符，判断正负符号，若是英文直接返回，若数字则不取。回文数题目描述判断一个整数是否是回文数。回文数是指正序从左向右和倒序从右向左读都是一样的整数。 JS算法题之leetcode(1~10) 前言一直以来，前端开发的知识储备在数据结构以及算法层面是有所暂缺的，可能归根于我们的前端开发的业务性质，但是我认为任何的编程岗位都离不开数据结构以及算法。因此，我作为...

SoapEye 2019-08-26 10:44 评论0 收藏0
LeetCode 206：反转链表 Reverse Linked List

摘要：反转一个单链表。示例输入输出进阶你可以迭代或递归地反转链表。你能否用两种方法解决这道题解题思路每次遍历到最后一位取节点这种方法就算了时间复杂度太高。从链表末尾向头部逐个分离节点，并将节点添加到新链表的末尾。与迭代法原理相似。反转一个单链表。 Reverse a singly linked list. 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2...

Gilbertat 2019-08-16 18:39 评论0 收藏0