目录
题目
题目链接
思路
复杂度
代码
题目
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
题目链接
25. K 个一组翻转链表 – 力扣（LeetCode）
https://leetcode.cn/problems/reverse-nodes-in-k-group/description/?envType=study-plan-v2&envId=top-100-liked
思路
计算链表长度：首先遍历一次链表，得到总节点数 length。
确定组数：需要翻转的组数为 length / k，因为最后一组如果不足 k 个节点则不翻转。
逐组翻转：
-
对于每一组，使用头插法将组内节点顺序反转。
-
初始时，prev 指向当前组的前一个节点（第一组前是虚拟头节点），curr 指向组的第一个节点。
-
在组内进行 k-1 次操作：每次将 curr 的下一个节点（即 next）移动到 prev 的后面，这样逐步将后面的节点提到前面，实现反转。
-
例如，对于链表 1->2->3->4，k=3，第一组为 1-2-3：
-
第一次操作：将 2 移到 prev 后，得到 2->1->3；
-
第二次操作：将 3 移到 prev 后，得到 3->2->1。
-
-
一组翻转完成后，prev 移动到当前组的最后一个节点（即原来的第一个节点），curr 移动到下一组的第一个节点，继续下一组。
返回结果：虚拟头节点的 next 即为新链表的头节点。
复杂度
-
时间复杂度：O(n)，其中 n 为链表长度。需要遍历一次链表计算长度，然后对每组进行翻转，每组内操作次数为 k-1，总组数为 n/k，因此总操作次数约为 n + (n/k)*(k-1) = 2n – n/k，仍为线性时间。
-
空间复杂度：O(1)，只使用了常数个额外指针，没有使用递归栈或额外数组。
代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
// 创建一个虚拟头节点，方便处理边界情况
ListNode* dummy = new ListNode(0);
dummy->next = head; // 虚拟头节点指向原链表头
ListNode* prev = dummy; // prev指向当前待翻转组的前一个节点
ListNode* curr = head; // curr指向当前组的第一个节点
ListNode* next; // 临时指针，用于保存要移动的节点
// 第一步：计算链表长度
int length = 0;
ListNode* temp = head; // 临时指针，避免修改head
while (temp) {
length++;
temp = temp->next;
}
// 第二步：循环处理每一组，组数为 length / k
for (int i = 0; i < length / k; i++) {
// 对当前组进行翻转，组内有k个节点，需要将后k-1个节点依次移到组首
for (int j = 0; j < k – 1; j++) {
// 将curr的下一个节点（即要移动的节点）保存到next
next = curr->next;
// 将curr的next指向next的下一个节点，跳过next
curr->next = next->next;
// 将next插入到prev之后（即组首位置）
next->next = prev->next;
prev->next = next;
// 注意：此时prev不变，curr也不变，但组内顺序已经变化
}
// 当前组翻转完成后，移动prev和curr到下一组
prev = curr; // prev指向当前组的最后一个节点（翻转后成为组尾）
curr = prev->next; // curr指向下一组的第一个节点
}
// 返回新链表的头节点（虚拟头节点的下一个）
return dummy->next;
}
};
