Preface
单链表的反转，按K反转等各种考点变体。
处理单链表时， 尽量采用递归实现：
1 因为递归代码简洁+优美，节省时间，并且不容易出错，是面试优选策略。
2 在面试时间比较宝贵的情况下，尽量预留时间展示自己的才能。
1 反转单链表(基础)
单链表结构定义如下：
1
2
3
4
5
6
|
// Definition for singly-linked list.
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
|
方法一: 递归实现(尾插法)
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
public:
//尾插法
ListNode* reverseList(ListNode* head) {
if(head == NULL || head->next == NULL) {
return head;
}
auto tail = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return tail; // became new head
}
};
|
方法二: 循环实现(头插法)
双指针,头插法:
1
2
3
4
5
6
7
8
9
10
11
|
ListNode* reverseList(ListNode *head) {
ListNode *pNewHead = NULL;
while(head != NULL){
auto pop = head;
head = head->next;
//插入新链表头部
pop->next = pNewHead;
pNewHead = pop;
}
return pNewHead; //链表的尾元素
}
|
2 变体一： 递归实现-从 m 到 n 中间节点的反转
上面我们使用递归，实现了反转整个链表的算法；
稍微改造下，只反转前k个元素(即递归深度到第k个元素，就可以返回)。
递归实现(从head 开始, 只反转前k个元素):
1
2
3
4
5
6
7
8
9
10
|
ListNode* reverseK(ListNode *head, int k) {
if (k <= 1) {
return head;
}
auto last = reverseK(head->next, k-1);
auto tail = head->next->next; //the tail list
head->next->next = head;
head->next = tail;
return last; //链表的尾元素
}
|
反转中间一部分[m,n], 再分析一下：
一种特殊情况是，m=1, 也就是反转前 n 个元素。
当 m = 2 ,我们把第一个节点去掉，就可以转化为上面的特殊情况了；
总结一下： 推广到一般的情况(m>1)，都可以转换为 m=1 的特殊情况处理。
1
2
3
4
5
6
7
8
|
// 反转中间一部分[m,n] 递归实现
ListNode* reverseBetween(ListNode *head, int m, int n) {
if (m == 1) {
return reverseK(head, n);
}
head->next = reverseBetween(head->next, m - 1, n - 1);
return head;
}
|
3 变体二: 按K个元素一组反转 (最后一组不足K个不反转)
我们先考虑下特殊情况:
1 链表元素总个数n 小于 k, 不做反转直接返回即可。
2 如果等于k个, 那么把当前链表按k反转，并返回新的head节点。
3 如果多余k个，我们先按照情形2处理前k个元素，剩下的(n-k)的链表当成一个子问题，执行步骤1,2,3.
最后这个子问题解决后，返回它的头指针 tailHead，
我们再把当前块的尾指针 head->next = tailHead 即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
// golang implements
func reverseKGroup(head *ListNode, k int) *ListNode {
p := head
for i := 0; i < k; i++ {
// 不足k个直接返回
if p == nil {
return head
}
p = p.Next
}
newHead := reverseK(head, k)
// 超过K个节点部分, 又是一个按K反转的问题
head.Next = reverseKGroup(p, k)
return newHead
}
// 反转链表前 K 个元素
func reverseK(head *ListNode, k int) *ListNode {
if k == 1 {
return head
}
rear := reverseK(head.Next, k-1)
head.Next.Next = head
head.Next = nil
return rear
}
|
这个问题还有一个变体(从后往前分组), 这个题是 Shopee(2019年)的面试题：
解决办法：
1 先把整个链表全部反转，然后从新的head开始，按照k个一组，执行前插法；
注意：最后一个分组不足k个，逐个元素进行前插法，即可保证不足k个不反转。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
/**[逆序] 从后往前, 每k个反转一次(不足k个不反转)（循环实现）
输入：1->2->3->4->5->6->7 k = 3
输出: 1->4->3->2->7->6->5
输入：1->2->3->4->5->6->7->8 k = 3
输出: 1->2->5->4->3->8->7->6
*/
ListNode* reverse(ListNode *head) {
if (head == NULL || head->next == NULL) {
return head;
}
ListNode *last = reverse(head->next);
head->next->next = head;
head->next = NULL;
return last; //became header
}
ListNode* reverseKGroup(ListNode *head, int k) {
ListNode * rhead = reverse(head);
int count = 0;
ListNode *cur = rhead;
ListNode *remain_list = rhead;
ListNode *newHead = NULL;
while (cur != NULL) {
++count;
ListNode *pre = cur;
cur = cur->next;
if (count == k) {
// 头插法
pre->next = newHead;
newHead = remain_list;
//move next
remain_list = cur;
count = 0;
}
}
//不足k个的部分,采用头插法
while (remain_list != NULL) {
ListNode *pop = remain_list;
remain_list = remain_list->next;
//头插法
pop->next = newHead;
newHead = pop;
}
return newHead;
}
|
总结
正所谓万变不离其宗，我们先分析问题的特殊场景，然后推广到一般；
把一般情况转化为一个个特殊场景的子问题，最后使用递归就可以完美解决。