题目描述
题目链接
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
进阶：
- 你可以设计一个只使用常数额外空间的算法来解决此问题吗？
- 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
算法1
(遍历一遍链表) $O(n)$
- 创建
dummy 节点来保存头结点
- k 个一组翻转链表：
- 首先判断接下来是否有 k 个节点，如果没有的话直接退出
- 类似于直接反转链表，两个一组，翻转即可，因此只需要翻转
k - 1 次
- 翻转结束，处理一些边界
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
|
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
auto dummy = new ListNode(-1);
dummy->next = head;
auto p = dummy;
for( ; p; )
{
auto q = p;
for(int i = 0; i < k && q; i ++) q = q->next;
if( !q) break;
auto a = p->next, b = a->next;
for(int i = 0; i < k - 1; i ++)
{
auto c = b->next;
b->next = a;
a = b;
b = c;
}
auto c = p->next;
p->next = a;
c->next = b;
p = c;
}
return dummy->next;
}
};
|
如果需要在反转结束后，将剩下的所有节点翻转呢？
(遍历一遍链表) $O(n)$
以 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
48
49
50
51
52
53
54
55
56
57
|
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
auto dummy = new ListNode(-1);
dummy->next = head;
auto p = dummy;
for( ; p; )
{
auto q = p;
for(int i = 0; i < k && q; i ++) q = q->next;
if( !q) break;
auto a = p->next, b = a->next;
for(int i = 0; i < k - 1; i ++)
{
auto c = b->next;
b->next = a;
a = b;
b = c;
}
auto c = p->next;
p->next = a;
c->next = b;
p = c;
}
auto t = p;
p = p->next;
auto q = p->next;
while( q)
{
auto a = q->next;
q->next = p;
p = q;
q = a;
}
t->next->next = NULL;
t->next = p;
return dummy->next;
}
};
|
