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.头尾节点的处理
- 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.除第一个节点外，递归将链表 reverse
- 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)$
相关题目
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
最近更新 1yr ago