🍍 25.k个一组翻转链表
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
注意，不足k个的链表不能翻转，也就是上面的[4,5]不能翻转
思路
基本思想
为了将链表中的节点k个一组进行翻转，同时不足k个的链表不能翻转，需要将链表中的节点进行分组，为了统一，先将不足k个的节点也翻转，之后如果判断出当前链表不足k个，那么就再翻转回来即可，翻转两次还是回到原来的形状
每形成一个翻转小链表，就将头结点保存到一个容器中，所有的节点翻转结束之后，将这些小链表合并成一个大链表
为了分组，需要记录当前遍历到了哪个节点上，一旦当前遍历到了第k个节点，说明形成了一个完整的翻转小链表，此时将这个小链表保存到容器中，同时重新开始翻转，翻转时使用了一个虚拟头结点，可以很好的记录当前翻转小链表的头结点
之后单独处理最后一个小链表，如果最后一个小链表的节点个数不足k个，那么就不能翻转，此时需要将其翻转回来
处理完所有的小链表之后，将其拼接在一起即可
执行流程
- 使用头插法进行链表翻转，虚拟头结点做辅助
- 当形成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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| class Solution {
public:
//每次取k个进行翻转，之后将翻转之后的小链表进行合并
//长度不足k的链表不进行翻转
ListNode* reverseKGroup(ListNode* head, int k) {
//只有一个节点
if(head->next==nullptr)
return head;
//到这里至少两个节点，每k次一存，之后重新开始翻转
vector<ListNode*> res;
ListNode* dummyHead=new ListNode(0);
dummyHead->next=nullptr;
ListNode* node=head;
ListNode* temp;
int index=0;
while(node!=nullptr){
if(index!=0&&index%k==0){
//保存每一个小翻转链表的头节点
res.push_back(dummyHead->next);
dummyHead->next=nullptr;
}
//反转
temp=node->next;
node->next=dummyHead->next;
dummyHead->next=node;
node=temp;
index++;
}
//处理最后一个小链表
if(index%k==0)
res.push_back(dummyHead->next);
//说明不足k个，不能反转，所以需要翻转回来,相当于还原
else{
node=dummyHead->next;
dummyHead->next=nullptr;
while(node!=nullptr){
temp=node->next;
node->next=dummyHead->next;
dummyHead->next=node;
node=temp;
}
res.push_back(dummyHead->next);
}
dummyHead->next=nullptr;
//小链表合并
for(int i=0;i<res.size();++i){
//刚开始使用dummyhead连接
if(i==0)
dummyHead->next=res[i];
//之后使用node连接
else{
node->next=res[i];
}
while(res[i]->next!=nullptr){
res[i]=res[i]->next;
}
//记住当前小链表的最后一个节点，与下一个小链表的头结点连接起来
node=res[i];
}
return dummyHead->next;
}
};
|
总结
将问题分割成一个一个的小问题，之后再合并，主要是最后一个小链表需要单独处理，之后全是代码模拟，每k个一翻转，之后将所有的小链表合并