C++实现LeetCode(25.每k个一组翻转链表)

前言LeetCode 25 要求给定链表头结点和整数 k每 k 个结点为一组进行翻转返回翻转后的链表如果最后剩余结点不足 k 个则保持原样。例如1-2-3-4-5、k 2结果是2-1-4-3-5k 3 时结果是3-2-1-4-5。这道题的难点不在翻转链表而在分组边界每一组翻转后前一组的尾要接上新组的头新组的尾要接上后一组的头。常见错误是只翻转了组内指针却忘了把组与组之间重新连起来导致链表断裂或成环。常见误解还有两个以为剩余不足 k 个也要翻转题目明确不翻以为可以先算出总长度再决定翻几组可以但没必要边扫边判断更直接。本文用迭代法实现额外空间 O(1)并解释每一步的指针含义。一、结点定义与整体框架// 适用于 C17struct ListNode {int val;ListNode *next;explicit ListNode(int x) : val(x), next(nullptr) {}};整体框架是在头结点前加一个哑结点dummy让第一组和后续组的处理完全一致。用groupPrev表示当前组的前一个结点每轮先找到当前组的第 k 个结点kth找不到说明剩余不足 k 个直接结束。// 适用于 C17ListNode *reverseKGroup(ListNode *head, int k){if (head nullptr || k 1) {return head;}ListNode dummy(0);dummy.next head;ListNode *groupPrev dummy;while (true) {ListNode *kth groupPrev;for (int i 0; i k kth ! nullptr; i) {kth kth-next;}if (kth nullptr) {break; // 剩余不足 k 个}ListNode *groupNext kth-next;ListNode *prev groupNext;ListNode *cur groupPrev-next;while (cur ! groupNext) {ListNode *tmp cur-next;cur-next prev;prev cur;cur tmp;}ListNode *newGroupPrev groupPrev-next; // 翻转前的组头现在是组尾groupPrev-next kth; // 前驱接上新组头groupPrev newGroupPrev; // 移到下一组之前}return dummy.next;}二、为什么要加哑结点如果没有哑结点第一组的前驱不存在翻转后还要单独修改head。加了哑结点后第一组的前驱就是dummy和后面每组一样代码里不需要任何特判。dummy是栈上的局部对象函数返回时它本身被销毁但dummy.next指向的是堆上的链表结点返回这个指针是安全的。不要返回dummy那才是悬垂指针。三、定位第 k 个结点kth从groupPrev出发走 k 步。走完 k 步后kth正好是当前组的最后一个结点。这里容易差一步如果从groupPrev-next出发走 k-1 步得到的是同一个结点但循环写法要相应调整。无论哪种判断不足 k 个的依据都是走完预定步数后指针是否为空。// 适用于 C17ListNode *kth groupPrev;for (int i 0; i k kth ! nullptr; i) {kth kth-next;}循环条件里的kth ! nullptr不能省。否则链表剩余不足 k 个时会对空指针解引用属于 UB。四、组内翻转翻转的范围是[groupPrev-next, groupNext)即从当前组第一个结点到组后第一个结点之前。用三个指针滚动prev初始为groupNext这样组尾翻转后会指向后一组cur初始为groupPrev-next即组头每轮先存cur-next把cur-next改成prev然后prev、cur一起前移当cur groupNext时整组翻转完毕prev指向原组尾也就是新组头。这个循环的终止条件必须是cur ! groupNext不能写成cur ! nullptr。后者会一路翻到链表末尾把不该翻的剩余部分也翻掉。翻转完成后kth是原组尾现在是新组头groupPrev-next原本指向原组头翻转后原组头变成组尾所以newGroupPrev groupPrev-next要在改指针之前保存把groupPrev-next指向kth完成前驱接新头groupPrev移到newGroupPrev准备处理下一组。顺序不能乱。如果先执行groupPrev-next kth再想取原组头就取不到了。五、走一遍示例以1-2-3-4-5、k 2 为例轮次groupPrevkthgroupNext翻转后新 groupPrev1dummy232-1-3121454-3-53335不足 k—不翻—最终dummy.next指向 2链表为2-1-4-3-5。第三轮时从groupPrev 3出发走 2 步第一步到 4第二步到 5再下一步为空不足一组退出。k 3 时第一组翻转1-2-3得到3-2-1接到 4剩余4-5不足 3 个保持原样结果是3-2-1-4-5。六、复杂度与递归写法迭代法扫描每个结点常数次时间 O(n)只用了几个指针变量额外空间 O(1)。递归写法更短先检查剩余是否够 k 个够就翻转前 k 个然后递归处理剩余部分并接到组尾。但递归深度是 n/kk 1 时深度为 n长链表有栈溢出风险。面试时可以先写递归再说明迭代版本更稳妥。维度迭代递归时间O(n)O(n)额外空间O(1)O(n/k) 调用栈代码长度较长较短长链表风险无栈溢出七、先统计长度的写法也可以先遍历一遍求出总长度 n算出完整组数n / k然后固定循环这么多次。这样每轮不必再判断剩余是否够 k 个因为循环次数已经保证了。// 适用于 C17int length 0;for (ListNode *p head; p ! nullptr; p p-next) {length;}const int groups length / k;for (int g 0; g groups; g) {// 此时一定存在完整的 k 个结点可以直接定位 kth}代价是多扫一遍链表时间仍是 O(n)只是常数变大。收益是循环条件更简单少了一层判空。两种写法都对面试时写哪种取决于你更想强调边扫边判断还是先算清楚再动手。如果链表长度在遍历过程中会变化本题不会先算长度的写法就不适用了。常见坑点❌ 翻转后忘记把前一组的尾接到新组头链表断裂。✅ 显式执行groupPrev-next kth;。❌ 组内循环终止条件写成cur ! nullptr把剩余不足 k 个的部分也翻了。✅ 终止条件用cur ! groupNext。❌ 找第 k 个结点时不判空剩余不足 k 个时解引用空指针。✅ 循环条件加kth ! nullptr走完检查是否为空。❌ 先改groupPrev-next再取原组头作为下一轮的groupPrev。✅ 先用newGroupPrev保存原组头再改指针。❌groupPrev更新成kth导致下一轮从错误位置开始。✅groupPrev应指向翻转后的组尾即原来的组头。❌ 返回dummy函数结束后栈对象销毁指针悬垂。✅ 返回dummy.next。❌ k 0 或负数时进入死循环或越界。✅ 开头判断k 1k 1 时原样返回。❌ 用std::vectorListNode *存结点再改值声称 O(1) 空间。✅ 那是 O(k) 额外空间指针原地翻转才是 O(1)。总结步骤操作关键点预处理建哑结点groupPrev dummy统一第一组与后续组定位从groupPrev走 k 步为空则剩余不足结束记边界groupNext kth-next翻转区间右开翻转prev groupNext起滚终止于cur groupNext重连前驱接kthgroupPrev移到原组头顺序不能反这道题的代码量不大但每一行都在处理边界。把哑结点、第 k 个结点、组后结点、原组头这四个位置记清楚再按先保存、后修改的顺序写指针就不会丢。