文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析2、解题代码三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接25.K 个一组翻转链表2、题目描述二、个人思路整理1、思路分析核心思路先统计总长用剩余长度控制循环每组内部用双指针原地翻转再完成组间拼接统计总长先遍历一遍链表求出总节点数n。之后每翻转一组就执行n - k只要n k就继续这样无需每次翻转前“先探路走k kk步”判断剩余节点是否够一组逻辑更简洁。初始化哨兵节点与组前驱指针dummy哨兵节点指向原始head避免第一组翻转后头节点发生变化、需要特殊处理让“头节点所在组被翻转”与“中间组被翻转”走同一套代码。p0当前组的前驱节点指向当前待翻转分组的前一个节点初始指向dummy每翻转完一组就移动到当前组的新尾巴。组内反转每进入新一组都在循环内部重新声明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依然指着当前组原本的头节点现在变成了当前组的尾节点。组间拼接与指针推进先用next_p0 p0-next暂存当前组的新尾因为下一步会覆盖p0-next。让当前组的新尾连上下一组的头p0-next-next cur;让上一组的尾巴连上当前组的新头p0-next pre;将p0推进到当前组的新尾即next_p0准备处理下一组。循环结束后返回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){intn0;ListNode*curhead;while(cur!nullptr){n;curcur-next;}ListNodedummy(0,head);ListNode*p0dummy;// p0指向当前组的前驱节点while(nk){n-k;// 每组重新开始翻转ListNode*prenullptr;ListNode*curp0-next;for(inti0;ik;i){ListNode*tmpcur-next;cur-nextpre;precur;curtmp;}// 组间拼接ListNode*next_p0p0-next;p0-next-nextcur;p0-nextpre;p0next_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 递归分组翻转迭代本题解法用dummyp0pre/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 2k2的特例可用同样的分组翻转框架也可用递归实现适合作为本题的热身。反转链表LeetCode 206本题组内反转的基础模板理解pre/cur双指针反转是解决本题的前提。反转链表 IILeetCode 92只翻转指定区间[ l e f t , r i g h t ] [left, right][left,right]与本题“定长分组翻转”互为补充可对比“区间边界定位”与“分组边界定位”的差异。K 个一组翻转链表递归写法同一道题的递归版本可与本题迭代写法对照体会“迭代控指针、递归控结构”的取舍。相关 LeetCode 例题206. 反转链表组内反转的基础模板92. 反转链表 II指定区间翻转对比24. 两两交换链表中的节点k 2 k2k2的特例143. 重排链表链表拆分与合并的综合应用
文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析2、解题代码三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接25.K 个一组翻转链表2、题目描述二、个人思路整理1、思路分析核心思路先统计总长用剩余长度控制循环每组内部用双指针原地翻转再完成组间拼接统计总长先遍历一遍链表求出总节点数n。之后每翻转一组就执行n - k只要n k就继续这样无需每次翻转前“先探路走k kk步”判断剩余节点是否够一组逻辑更简洁。初始化哨兵节点与组前驱指针dummy哨兵节点指向原始head避免第一组翻转后头节点发生变化、需要特殊处理让“头节点所在组被翻转”与“中间组被翻转”走同一套代码。p0当前组的前驱节点指向当前待翻转分组的前一个节点初始指向dummy每翻转完一组就移动到当前组的新尾巴。组内反转每进入新一组都在循环内部重新声明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依然指着当前组原本的头节点现在变成了当前组的尾节点。组间拼接与指针推进先用next_p0 p0-next暂存当前组的新尾因为下一步会覆盖p0-next。让当前组的新尾连上下一组的头p0-next-next cur;让上一组的尾巴连上当前组的新头p0-next pre;将p0推进到当前组的新尾即next_p0准备处理下一组。循环结束后返回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){intn0;ListNode*curhead;while(cur!nullptr){n;curcur-next;}ListNodedummy(0,head);ListNode*p0dummy;// p0指向当前组的前驱节点while(nk){n-k;// 每组重新开始翻转ListNode*prenullptr;ListNode*curp0-next;for(inti0;ik;i){ListNode*tmpcur-next;cur-nextpre;precur;curtmp;}// 组间拼接ListNode*next_p0p0-next;p0-next-nextcur;p0-nextpre;p0next_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 递归分组翻转迭代本题解法用dummyp0pre/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 2k2的特例可用同样的分组翻转框架也可用递归实现适合作为本题的热身。反转链表LeetCode 206本题组内反转的基础模板理解pre/cur双指针反转是解决本题的前提。反转链表 IILeetCode 92只翻转指定区间[ l e f t , r i g h t ] [left, right][left,right]与本题“定长分组翻转”互为补充可对比“区间边界定位”与“分组边界定位”的差异。K 个一组翻转链表递归写法同一道题的递归版本可与本题迭代写法对照体会“迭代控指针、递归控结构”的取舍。相关 LeetCode 例题206. 反转链表组内反转的基础模板92. 反转链表 II指定区间翻转对比24. 两两交换链表中的节点k 2 k2k2的特例143. 重排链表链表拆分与合并的综合应用
