# 0206. 反转链表
### 题目地址(206. 反转链表)
### 题目描述
反转一个单链表。
```
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
```
### 前置知识
* [链表](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/thinkings/basic-data-structure)
### 公司
* 阿里
* 百度
* 腾讯
* adobe
* amazon
* apple
* bloomberg
* facebook
* microsoft
* snapchat
* twitter
* uber
* yahoo
* yelp
* zenefits
### 思路
这个就是常规操作了，使用一个变量记录前驱 pre，一个变量记录后继 next，不断更新`current.next = pre` 就好了。
链表的题目 90% 的 bug 都出现在：
1. 头尾节点的处理
2. 指针循环引用导致死循环
因此大家对这两个问题要保持 100% 的警惕。
### 关键点解析
* 链表的基本操作（交换）
* 虚拟节点 dummy 简化操作
* 注意更新 current 和 pre 的位置， 否则有可能出现溢出
### 代码
语言支持：JS, C++, Python,Java
JavaScript Code：
```js
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function (head) {
if (!head || !head.next) return head;
let cur = head;
let pre = null;
while (cur) {
const next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
};
```
C++ Code：
```
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* prev = NULL;
ListNode* cur = head;
ListNode* next = NULL;
while (cur != NULL) {
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
};
```
Python Code:
```python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head: return None
prev = None
cur = head
while cur:
cur.next, prev, cur = prev, cur, cur.next
return prev
```
Java Code:
```java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null, cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
```
**复杂度分析**
* 时间复杂度：$O(N)$
* 空间复杂度：$O(1)$
### 拓展
通过单链表的定义可以得知，单链表也是递归结构，因此，也可以使用递归的方式来进行 reverse 操作。
> 由于单链表是线性的，使用递归方式将导致栈的使用也是线性的，当链表长度达到一定程度时，递归会导致爆栈，因此，现实中并不推荐使用递归方式来操作链表。
1. 除第一个节点外，递归将链表 reverse
2. 将第一个节点添加到已 reverse 的链表之后
> 这里需要注意的是，每次需要保存已经 reverse 的链表的头节点和尾节点
C++实现
```
// 普通递归
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* tail = nullptr;
return reverseRecursive(head, tail);
}
ListNode* reverseRecursive(ListNode *head, ListNode *&tail) {
if (head == nullptr) {
tail = nullptr;
return head;
}
if (head->next == nullptr) {
tail = head;
return head;
}
auto h = reverseRecursive(head->next, tail);
if (tail != nullptr) {
tail->next = head;
tail = head;
head->next = nullptr;
}
return h;
}
};
// （类似）尾递归
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == nullptr) return head;
return reverseRecursive(nullptr, head, head->next);
}
ListNode* reverseRecursive(ListNode *prev, ListNode *head, ListNode *next)
{
if (next == nullptr) return head;
auto n = next->next;
next->next = head;
head->next = prev;
return reverseRecursive(head, next, n);
}
};
```
JavaScript 实现
```javascript
var reverseList = function (head) {
// 递归结束条件
if (head === null || head.next === null) {
return head;
}
// 递归反转 子链表
let newReverseList = reverseList(head.next);
// 获取原来链表的第 2 个节点 newReverseListTail
let newReverseListTail = head.next;
// 调整原来头结点和第 2 个节点的指向
newReverseListTail.next = head;
head.next = null;
// 将调整后的链表返回
return newReverseList;
};
```
Python 实现
```python
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head or not head.next: return head
ans = self.reverseList(head.next)
head.next.next = head
head.next = None
return ans
```
**复杂度分析**
* 时间复杂度：$O(N)$
* 空间复杂度：$O(N)$
### 相关题目
* [92.reverse-linked-list-ii](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/92.reverse-linked-list-ii)
* [25.reverse-nodes-in-k-groups](https://github.com/azl397985856/leetcode/blob/master/problems/25.reverse-nodes-in-k-groups-cn.md)
更多题解可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
