【算法面试必刷】25. K 个一组翻转链表
目录
题目
题目链接
思路
复杂度
代码
题目
给你链表的头节点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; } };