leetcode0025 K个一组翻转链表 - hard

1 题目： K个一组翻转链表

官方标定难度：难

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将末了剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要现实进行节点互换。
示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
示例 2：

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]
提示：

链表中的节点数目为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000
进阶：你可以计划一个只用 O(1) 额外内存空间的算法解决此题目吗？

2 solution

如果直接修改指针指向会很贫苦，也很轻易堕落，但是如果先将全部的指针都存储下来，然后按照数组的方式修改就比较简单了。
主要完成以下工作：
1 组内指针方向翻转
2 组间衔接
3 head 修改
4 末了组分环境讨论
代码

1. ListNode *reverseKGroup(ListNode *head, int k) {
2.     if(k == 1) return head;
3.     vector<ListNode *> list;
4.     ListNode * h = head;
6.     while (h) {
7.         list.push_back(h);
8.         h = h->next;
9.     }
11.     if(list.size() < k){
12.         return head;
13.     }
15.     head = list[k - 1];
16.     int i;
18.     for (i = 0; i + k - 1 < list.size(); i += k) { // i = 0 2
19.         // i = 2; j = 3 ->
20.         for (int j = i + k - 1; j > i; j--) {
21.             list[j]->next = list[j - 1];
22.         }
23.         if (i > 0) // i = 2 [1<-2,3<-4,5]
24.             list[i - k]->next = list[i + k - 1];
25.     }
27.     if(i < list.size()) // i = 4
28.         list[i - k]->next = list[i];
29.     else
30.         list[i - k]->next = nullptr;
32.     return head;
33. }

复制代码

结果

3 进阶

你可以计划一个只用 O(1) 额外内存空间的算法解决此题目吗？

这里就不答应我们将全部节点都保存到数组中，只能保存若干个点。我选择保存需要衔接的节点。包括上一组的开始，下一组的开始， 本组的开始，本组的结尾，还有当前节点，上一个节点，下一个节点。
然后按照以下顺序编写。
1 标志好当前组的开头

2 找到当前组的结尾

3 从本组开头一次翻转指向

4 将上一组衔接到本组

5 主要开头在哪

6 结尾特别讨论

1. ListNode *reverseKGroup(ListNode *head, int k) { // k >= 1
2.     if (k == 1) return head;
3.     ListNode *last_head, *cur_head, *cur_tail, *next_head, *last, *now = head, *next;
4.     int i = 0;
6.     while (true) {
7.         i++;
8.         if (i % k == 0) {
9.             cur_tail = now;
10.             next_head = now->next;
12.             // 翻转
13.             last = cur_head;
14.             now = last->next;
15.             while (now != next_head) {
16.                 next = now->next;
17.                 now->next = last;
18.                 last = now;
19.                 now = next;
20.             }
22.             // 处理尾部
23.             if (i > k)
24.                 last_head->next = cur_tail;
25.             else {
26.                 head = cur_tail;
27.             }
29.             last_head = cur_head;
30.             now = next_head;
31.             // cur_head = now;
32.             i++;
33.             if (now == nullptr) {
34.                 cur_head->next = nullptr;
35.                 return head;
36.             }
37.         }
39.         if (i % k == 1) {
40.             cur_head = now;
41.         }
43.         if (i % k != 0)
44.             now = now->next;
46.         if (now == nullptr) {
47.             last_head->next = cur_head;
48.             break;
49.         }
50.     }
51.     return head;
52. }

复制代码

结果

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。