0206. 反转链表

题目地址(206. 反转链表)

题目描述

反转一个单链表。
1
示例:
2
3
输入: 1->2->3->4->5->NULL
4
输出: 5->4->3->2->1->NULL
5
进阶:
6
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?
Copied!

前置知识

公司

  • 阿里
  • 百度
  • 腾讯
  • adobe
  • amazon
  • apple
  • bloomberg
  • facebook
  • microsoft
  • snapchat
  • twitter
  • uber
  • yahoo
  • yelp
  • zenefits

思路

这个就是常规操作了,使用一个变量记录前驱 pre,一个变量记录后继 next,不断更新current.next = pre 就好了。
链表的题目 90% 的 bug 都出现在:
  1. 1.
    头尾节点的处理
  2. 2.
    指针循环引用导致死循环
因此大家对这两个问题要保持 100% 的警惕。

关键点解析

  • 链表的基本操作(交换)
  • 虚拟节点 dummy 简化操作
  • 注意更新 current 和 pre 的位置, 否则有可能出现溢出

代码

语言支持:JS, C++, Python,Java
JavaScript Code:
1
/**
2
* Definition for singly-linked list.
3
* function ListNode(val) {
4
* this.val = val;
5
* this.next = null;
6
* }
7
*/
8
/**
9
* @param {ListNode} head
10
* @return {ListNode}
11
*/
12
var reverseList = function (head) {
13
if (!head || !head.next) return head;
14
15
let cur = head;
16
let pre = null;
17
18
while (cur) {
19
const next = cur.next;
20
cur.next = pre;
21
pre = cur;
22
cur = next;
23
}
24
25
return pre;
26
};
Copied!
C++ Code:
1
/**
2
* Definition for singly-linked list.
3
* struct ListNode {
4
* int val;
5
* ListNode *next;
6
* ListNode(int x) : val(x), next(NULL) {}
7
* };
8
*/
9
class Solution {
10
public:
11
ListNode* reverseList(ListNode* head) {
12
ListNode* prev = NULL;
13
ListNode* cur = head;
14
ListNode* next = NULL;
15
while (cur != NULL) {
16
next = cur->next;
17
cur->next = prev;
18
prev = cur;
19
cur = next;
20
}
21
return prev;
22
}
23
};
Copied!
Python Code:
1
# Definition for singly-linked list.
2
# class ListNode:
3
# def __init__(self, x):
4
# self.val = x
5
# self.next = None
6
7
class Solution:
8
def reverseList(self, head: ListNode) -> ListNode:
9
if not head: return None
10
prev = None
11
cur = head
12
while cur:
13
cur.next, prev, cur = prev, cur, cur.next
14
return prev
Copied!
Java Code:
1
/**
2
* Definition for singly-linked list.
3
* public class ListNode {
4
* int val;
5
* ListNode next;
6
* ListNode(int x) { val = x; }
7
* }
8
*/
9
class Solution {
10
public ListNode reverseList(ListNode head) {
11
ListNode pre = null, cur = head;
12
13
while (cur != null) {
14
ListNode next = cur.next;
15
cur.next = pre;
16
pre = cur;
17
cur = next;
18
}
19
20
return pre;
21
}
22
}
Copied!
复杂度分析
  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(1)$

拓展

通过单链表的定义可以得知,单链表也是递归结构,因此,也可以使用递归的方式来进行 reverse 操作。
由于单链表是线性的,使用递归方式将导致栈的使用也是线性的,当链表长度达到一定程度时,递归会导致爆栈,因此,现实中并不推荐使用递归方式来操作链表。
  1. 1.
    除第一个节点外,递归将链表 reverse
  2. 2.
    将第一个节点添加到已 reverse 的链表之后
这里需要注意的是,每次需要保存已经 reverse 的链表的头节点和尾节点
C++实现
1
// 普通递归
2
class Solution {
3
public:
4
ListNode* reverseList(ListNode* head) {
5
ListNode* tail = nullptr;
6
return reverseRecursive(head, tail);
7
}
8
9
ListNode* reverseRecursive(ListNode *head, ListNode *&tail) {
10
if (head == nullptr) {
11
tail = nullptr;
12
return head;
13
}
14
if (head->next == nullptr) {
15
tail = head;
16
return head;
17
}
18
auto h = reverseRecursive(head->next, tail);
19
if (tail != nullptr) {
20
tail->next = head;
21
tail = head;
22
head->next = nullptr;
23
}
24
return h;
25
}
26
};
27
28
// (类似)尾递归
29
class Solution {
30
public:
31
ListNode* reverseList(ListNode* head) {
32
if (head == nullptr) return head;
33
return reverseRecursive(nullptr, head, head->next);
34
}
35
36
ListNode* reverseRecursive(ListNode *prev, ListNode *head, ListNode *next)
37
{
38
if (next == nullptr) return head;
39
auto n = next->next;
40
next->next = head;
41
head->next = prev;
42
return reverseRecursive(head, next, n);
43
}
44
};
Copied!
JavaScript 实现
1
var reverseList = function (head) {
2
// 递归结束条件
3
if (head === null || head.next === null) {
4
return head;
5
}
6
7
// 递归反转 子链表
8
let newReverseList = reverseList(head.next);
9
// 获取原来链表的第 2 个节点 newReverseListTail
10
let newReverseListTail = head.next;
11
// 调整原来头结点和第 2 个节点的指向
12
newReverseListTail.next = head;
13
head.next = null;
14
15
// 将调整后的链表返回
16
return newReverseList;
17
};
Copied!
Python 实现
1
class Solution:
2
def reverseList(self, head: ListNode) -> ListNode:
3
if not head or not head.next: return head
4
ans = self.reverseList(head.next)
5
head.next.next = head
6
head.next = None
7
return ans
Copied!
复杂度分析
  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(N)$

相关题目

更多题解可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。