LeetCode Hard｜【25. K 个一组翻转链表】

力扣题目链接

首先我们考虑一种很直观的思路：

• 遍历链表，统计链表长度
• 遍历链表，进行翻转
  • 对于每一组长度为 K 的节点，进行翻转
  • 如果剩余节点不足 K 个，则不进行翻转
• 连接翻转后的子链表
  这里我们用的就是只用 O(1) 额外内存空间的算法

关于如何 k 个节点个数的链表

我认为这里最重要的是链表的翻转，当你知道需要翻转的链表长度的时候，这个方法应该按照固定模版来进行，也就是我们的三指针：

for (int i = 1; i < k; i++) {cur->next = nex->next;nex->next = pre->next;pre->next = nex;nex = cur->next;
}

但是还记得我们之前在做反转链表题目的时候是怎么处理的嘛：

while (cur) {ListNode *nex = cur->next;cur->next = pre;pre = cur;cur = nex;
}

这里简单直观多了，最大的区别是什么呢？

首先，做整表翻转的时候，我们的逻辑非常简单
其次，对于对 k 个节点分组翻转，并且我们还必须做到对剩余的 k 个节点不进行翻转，势必有这样形式的代码：

while (cout >= k) {...for (...) {...}...count -= k;
}

CPP总体代码：

class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {if (!head || k == 1) return head;ListNode *dummyHead = new ListNode();dummyHead->next = head;ListNode *cur = dummyHead, *pre = dummyHead, *nex = dummyHead;int count = 0;cur = head;while (cur) {cur = cur->next;count++;}while (count >= k) {cur = pre->next;nex = cur->next;for (int i = 1; i < k; i++) {cur->next = nex->next;nex->next = pre->next;pre->next = nex;nex = cur->next;}pre = cur;count -= k;}return dummyHead->next;}
};