IT评测·应用市场-qidao123.com技术社区

标题: leetcode0025 K个一组翻转链表 - hard [打印本页]
作者: 没腿的鸟    时间: 2025-3-25 18:47
标题: 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企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/) Powered by Discuz! X3.4