考点
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == nullptr) return nullptr;
ListNode *dummyHead = new ListNode(-1, head);
while (head->next != nullptr) {
ListNode *tmp = head->next;
head->next = tmp->next;
tmp->next = dummyHead->next;
dummyHead->next = tmp;
}
return dummyHead->next;
}
};
|
思路
朴素法：更改方向
迭代
反转一个链表，很容易想到更改方向即可，毕竟方向是由next值决定的
比如要反转链表{1, 2, 3, 4}
很自然地想到让每个节点指向前一个节点即可
代码实现很简单。令一个指针cur指向当前节点，一个指针prev指向前一个节点；指针prev初始值为nullptr，代表新表尾
每次都令cur节点的next值指向prev，然后两个指针一齐向后移
当cur节点为空时，prev恰好指向最后一个节点，即新方向链表的表头
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *cur = head;
ListNode *prev = nullptr;
while(cur != nullptr){
ListNode *tmp = cur->next;
cur->next = prev;
prev = cur;
cur = tmp;
}
return prev;
}
};
|
递归
当然可以将其修改为递归，按照以下四部曲来
子问题：当前节点需指向前一个节点
递归语句顺序：递归方向分为一去一回，去方向至临界值返回；在这里两种方向都可以
去方向类似迭代，同样不知道上个节点的信息，所以必须通过传参记录上个节点的地址
回方向则可以令当前节点的下一个节点指向自己，达到改变方向的效果
返回值：分为去方向和回方向两种
由于去方向类似迭代，要获得新表头必须到达临界值，所以递归语句必须放在程序结构的最后一行再返回
回方向的新表头到达临界值返回即可
临界点：到达最后一个节点后开始回方向
去方向的递归代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
ListNode* recursiveFunc(ListNode *head, ListNode *prev) {
if (head == nullptr) return prev;
ListNode *tmp = head->next;
head->next = prev;
return recursiveFunc(tmp, head);
}
ListNode* reverseList(ListNode* head) {
return recursiveFunc(head, nullptr);
}
};
|
回方向的递归代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == nullptr) return nullptr;
if (head->next == nullptr) return head;
ListNode *newHead = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return newHead;
}
};
|
头插法
头插法是反转链表算法中最通用的处理方式，请务必掌握
我们知道，操作链表基本都会新增dummyHead伪节点，以避免讨论头结点的特殊情况
头插法则是参考了dummyHead的精髓，在待逆转链表的表头的前一个节点做文章
以链表{1, 2, 3, 4,
5}为例，若反转整个链表，则新建dummyHead伪节点于节点1前；若反转子链表{3,
4}，则需要节点2做配合
下面分别介绍市面上普通的头插法和我改进的头插法
普通头插法
普通头插法的局限性在于无法反转子链表；假设需要反转链表{1, 2, 3}
首先新增一个dummyHead伪节点，指向nullptr
随后，每个节点都插入到dummyHead后面即可完成反转链表
代码如下，比较简单
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *dummyHead = new ListNode(-1);
while (head != nullptr) {
ListNode *tmp = head->next;
head->next = dummyHead->next;
dummyHead->next = head;
head = tmp;
}
return dummyHead->next;
}
};
|
改进版头插法
我改进后的头插法可以反转任意子链表，适用性极强
具体步骤如下：
- 选取待反转链表头节点的前一个节点作为
dummyHead，如果没有则新增
- 头节点是反转链表后的尾节点；故而每次将头节点的后一个节点插入至
dummyHead后
以反转{1, 2, 3, 4, 5}的子链表{2, 3, 4}为例：
选取节点1作为dummyHead，节点2为子链表表头head
真正需要移动的则是节点cur，代表节点head的下一个节点
每次将节点cur插入至dummyHead节点之后即可
根据上述步骤描述，很容易就能写出代码了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == nullptr) return nullptr;
ListNode *dummyHead = new ListNode(-1, head);
while (head->next != nullptr) {
ListNode *tmp = head->next;
head->next = tmp->next;
tmp->next = dummyHead->next;
dummyHead->next = tmp;
}
return dummyHead->next;
}
};
|