【链表】LC 25.K 个一组翻转链表

前言

本专栏文章为《LeetCode 热题 100》的刷题题解，相关内容如有侵权，立即删除。

一、题目

1、原题链接

25.K 个一组翻转链表

2、题目描述

二、个人思路整理

1、思路分析

核心思路：先统计总长，用剩余长度控制循环，每组内部用双指针原地翻转，再完成组间拼接：

1. 统计总长：先遍历一遍链表求出总节点数n。之后每翻转一组就执行n -= k，只要n >= k就继续，这样无需每次翻转前“先探路走k kk步”判断剩余节点是否够一组，逻辑更简洁。

2. 初始化哨兵节点与组前驱指针：

   • dummy：哨兵节点，指向原始head，避免第一组翻转后头节点发生变化、需要特殊处理，让“头节点所在组被翻转”与“中间组被翻转”走同一套代码。
   • p0：当前组的前驱节点，指向当前待翻转分组的前一个节点，初始指向dummy；每翻转完一组，就移动到当前组的新尾巴。

3. 组内反转：

   • 每进入新一组，都在循环内部重新声明pre = nullptr、cur = p0->next，保证每组从干净状态开始翻转。
   • pre：已经翻转的部分指向反转链表的前一个节点，最终指向当前组的新头。
   • cur：当前正在处理的节点，指向当前需要翻转的节点，最终停在下一组的头节点。
   • 用for (int i = 0; i < k; i++)循环k kk次，执行最基础的链表反转（tmp = cur->next; cur->next = pre; pre = cur; cur = tmp;）。
   • k kk次循环结束后，pre停在当前组的新头节点，cur停在下一组的头节点，而p0->next依然指着当前组原本的头节点（现在变成了当前组的尾节点）。

4. 组间拼接与指针推进：

   • 先用next_p0 = p0->next暂存当前组的新尾，因为下一步会覆盖p0->next。
   • 让当前组的新尾连上下一组的头：p0->next->next = cur;
   • 让上一组的尾巴连上当前组的新头：p0->next = pre;
   • 将p0推进到当前组的新尾（即next_p0），准备处理下一组。

5. 循环结束后返回dummy.next：由于头节点所在组可能已被翻转，最终头节点不一定是原head，必须返回哨兵的后继。

2、解题代码

/** * 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) {} * }; */classSolution{public:ListNode*reverseKGroup(ListNode*head,intk){intn=0;ListNode*cur=head;while(cur!=nullptr){n++;cur=cur->next;}ListNodedummy(0,head);ListNode*p0=&dummy;// p0指向当前组的前驱节点while(n>=k){n-=k;// 每组重新开始翻转ListNode*pre=nullptr;ListNode*cur=p0->next;for(inti=0;i<k;i++){ListNode*tmp=cur->next;cur->next=pre;pre=cur;cur=tmp;}// 组间拼接ListNode*next_p0=p0->next;p0->next->next=cur;p0->next=pre;p0=next_p0;}returndummy.next;}};

复杂度分析

• 时间复杂度：O ( N ) O(N)O(N)，遍历两次，一次算长度，一次做翻转。
• 空间复杂度：O ( 1 ) O(1)O(1)，仅在栈上分配了一个dummy对象和几个指针。

三、知识风暴

链表分组翻转（Reverse Nodes in k-Group）是本题的核心：题目要求把链表每k kk个节点视为一组，组内原地翻转，不足k kk个的尾部保持原样。它本质上是「基础链表反转」的升级版——把一次整体反转拆成若干次定长反转，并在组与组之间做好衔接。

算法核心思想：

• 先统计总长，用长度控制循环：先遍历一遍求出节点总数n，之后每翻转一组就执行n -= k，只要n >= k就继续。这样无需每次翻转前“探路走k kk步”判断剩余节点是否够一组，逻辑更简洁。
• 哨兵节点统一边界：引入dummy指向head，让“头节点所在组被翻转”与“中间组被翻转”走同一套代码，避免单独处理头节点。
• 组内头插式反转：在每组内部用pre/cur双指针循环k kk次完成反转，k kk次结束后pre是新头、cur是下一组的头，而p0->next仍指向本组旧头（即反转后的新尾）。
• 两步完成衔接：p0->next->next = cur让本组新尾接上下一组；p0->next = pre让上一组尾巴接上本组新头；最后把p0推进到本组新尾，准备处理下一组。

常见对比：迭代原地翻转 vs 递归分组翻转

• 迭代（本题解法）：用dummy+p0+pre/cur在链表上原地操作，空间复杂度O ( 1 ) O(1)O(1)，是面试中最推荐的写法；但指针较多，衔接顺序写错容易断链，需要理清“新头 / 新尾 / 下一组头”三者的关系。
• 递归分组翻转：先判断剩余节点是否够k kk个，够则翻转前k kk个，再递归处理后续部分并把本组新尾指向递归结果。代码更短、更贴近分治直觉，但递归深度为O ( n / k ) O(n/k)O(n/k)，存在栈开销。
• 借助数组 / 栈：把每组节点值压入栈再弹出重写，思路直观、不易出错，但需要额外O ( k ) O(k)O(k)空间，且只改值不改节点，不符合“原地翻转节点”的题意要求。

指针衔接的关键细节：

• 为什么先存next_p0：执行p0->next = pre之后，原来的p0->next（本组新尾）就被覆盖了，所以必须先用next_p0暂存，再把它作为下一轮的p0。
• pre的复位：每进入新一组前，pre需要重新置为nullptr，否则会把上一组的节点错误地接到本组新头之后。
• 不足k kk个的处理：由于循环条件是n >= k，剩余不足k kk个的节点根本不会进入翻转逻辑，天然保持原顺序，无需额外判断。

使用要点：

• 长度先行：先算n再翻转，是本题最省心的写法，务必牢记这个“用总长度控制循环”的套路。
• 哨兵节点必备：凡是涉及“可能翻转头节点”的链表题，dummy都是降低边界复杂度的利器。
• 画图验证指针：组内反转 + 组间衔接共涉及 4 个指针，建议在纸上画出dummy -> 组1 -> 组2的示意图，逐步核对每一步的指向。
• 返回dummy.next：最终头节点可能已不是原head，必须返回dummy.next而非head。

算法变体与扩展：

• 两两交换链表中的节点（LeetCode 24）：即k = 2 k = 2k=2的特例，可用同样的分组翻转框架，也可用递归实现，适合作为本题的热身。
• 反转链表（LeetCode 206）：本题组内反转的基础模板，理解pre/cur双指针反转是解决本题的前提。
• 反转链表 II（LeetCode 92）：只翻转指定区间[ l e f t , r i g h t ] [left, right][left,right]，与本题“定长分组翻转”互为补充，可对比“区间边界定位”与“分组边界定位”的差异。
• K 个一组翻转链表（递归写法）：同一道题的递归版本，可与本题迭代写法对照，体会“迭代控指针、递归控结构”的取舍。

相关 LeetCode 例题：

• 206. 反转链表（组内反转的基础模板）
• 92. 反转链表 II（指定区间翻转对比）
• 24. 两两交换链表中的节点（k = 2 k=2k=2的特例）
• 143. 重排链表（链表拆分与合并的综合应用）