LeetCode 之 JavaScript 解答第206题 —— 反转链表（Reverse Linked List）

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

▉ 算法思路

▉ 测试用例

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...

欢迎关注我个人公众号：「一个不甘平凡的码农」，记录了自己一路自学编程的故事。