leetcode0025 K个一组翻转链表 - hard
1 题目： K个一组翻转链表官方标定难度：难
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将末了剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要现实进行节点互换。
示例 1：
https://i-blog.csdnimg.cn/direct/0be5cf6068d34e1da5e577fba25262e5.png
输入：head = , k = 2
输出：
示例 2：
https://i-blog.csdnimg.cn/direct/2dd16f3c77884de882631ccf4fb96f65.png
输入：head = , k = 3
输出：
提示：
链表中的节点数目为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000
进阶：你可以计划一个只用 O(1) 额外内存空间的算法解决此题目吗？
2 solution
如果直接修改指针指向会很贫苦，也很轻易堕落，但是如果先将全部的指针都存储下来，然后按照数组的方式修改就比较简单了。
主要完成以下工作：
1 组内指针方向翻转
2 组间衔接
3 head 修改
4 末了组分环境讨论
代码
ListNode *reverseKGroup(ListNode *head, int k) {
if(k == 1) return head;
vector<ListNode *> list;
ListNode * h = head;
while (h) {
list.push_back(h);
h = h->next;
}
if(list.size() < k){
return head;
}
head = list;
int i;
for (i = 0; i + k - 1 < list.size(); i += k) { // i = 0 2
// i = 2; j = 3 ->
for (int j = i + k - 1; j > i; j--) {
list->next = list;
}
if (i > 0) // i = 2
list->next = list;
}
if(i < list.size()) // i = 4
list->next = list;
else
list->next = nullptr;
return head;
}
结果
https://i-blog.csdnimg.cn/direct/db6b5aa9500048dc814b545437610445.png
3 进阶
你可以计划一个只用 O(1) 额外内存空间的算法解决此题目吗？
这里就不答应我们将全部节点都保存到数组中，只能保存若干个点。我选择保存需要衔接的节点。包括上一组的开始，下一组的开始， 本组的开始，本组的结尾，还有当前节点，上一个节点，下一个节点。
然后按照以下顺序编写。
1 标志好当前组的开头
2 找到当前组的结尾
3 从本组开头一次翻转指向
4 将上一组衔接到本组
5 主要开头在哪
6 结尾特别讨论
ListNode *reverseKGroup(ListNode *head, int k) { // k >= 1
if (k == 1) return head;
ListNode *last_head, *cur_head, *cur_tail, *next_head, *last, *now = head, *next;
int i = 0;
while (true) {
i++;
if (i % k == 0) {
cur_tail = now;
next_head = now->next;
// 翻转
last = cur_head;
now = last->next;
while (now != next_head) {
next = now->next;
now->next = last;
last = now;
now = next;
}
// 处理尾部
if (i > k)
last_head->next = cur_tail;
else {
head = cur_tail;
}
last_head = cur_head;
now = next_head;
// cur_head = now;
i++;
if (now == nullptr) {
cur_head->next = nullptr;
return head;
}
}
if (i % k == 1) {
cur_head = now;
}
if (i % k != 0)
now = now->next;
if (now == nullptr) {
last_head->next = cur_head;
break;
}
}
return head;
}
结果
https://i-blog.csdnimg.cn/direct/4f4e92cb78374f9287ff6d5bec1626b1.png
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]