leetcode 链接：K 个一组翻转链表
《程序员代码面试指南》左程云 中相同题目：★★☆☆将单链表的每 K 个节点之间逆序

题目

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

进阶：
你可以设计一个只使用常数额外空间的算法来解决此问题吗？
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

解答 & 代码

每次数 K 个节点翻转

注意：代码第42-48行
image.png

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */
  11. class Solution {
  12. private: 
  13.     // 将 preHead 和 afterHead 之间的节链表翻转（不包含这两个节点本身）
  14.     void reverseList(ListNode* preHead, ListNode* afterEnd)
  15.     {
  16.         if(preHead == nullptr || preHead->next == afterEnd || preHead->next->next == afterEnd)
  17.             return;
  18.         ListNode* pre = afterEnd;
  19.         ListNode* cur = preHead->next;
  20.         while(cur != afterEnd)
  21.         {
  22.             ListNode* next = cur->next;
  23.             cur->next = pre;
  24.             pre = cur;
  25.             cur = next;
  26.         }
  27.         preHead->next = pre;
  28.     }
  29. public:
  30.     ListNode* reverseKGroup(ListNode* head, int k) {
  31.         ListNode* dummyHead = new ListNode(-1, head);
  32.         ListNode* preHead = dummyHead;
  33.         ListNode* cur = head;
  34.         int cnt = 0;
  35.         while(cur != nullptr)
  36.         {
  37.             ++cnt;
  38.             if(cnt < k)
  39.                 cur = cur->next;
  40.             else
  41.             {
  42.                 // 注意在反转完 k 个节点后，cur 节点的情况有所变化，因此要先保存下一步的 preHead 和 next
  43.                 ListNode* newPreHead = preHead->next;
  44.                 ListNode* next = cur->next;
  45.                 reverseList(preHead, cur->next);
  46.                 preHead = newPreHead;
  47.                 cur = next;
  48.                 cnt = 0;
  49.             }
  50.         }
  51.         return dummyHead->next;
  52.     }
  53. };

执行结果：

  1. 执行结果：通过
  3. 执行用时：20 ms, 在所有 C++ 提交中击败了 66.26% 的用户
  4. 内存消耗：11.1 MB, 在所有 C++ 提交中击败了 64.05% 的用户