LeetCode 25. K 个一组翻转链表 | 硬核拆解「reverse N」核心思路
✨ LeetCode 25. K 个一组翻转链表 | 硬核拆解「reverse N」核心思路
- 视频地址
- 🔍 一、问题核心含义：K 个一组翻转链表
- 📊 二、算法原理：基于「reverse N」的分层实现
- 💡 三、整体实现框架：虚拟头节点 + 双指针循环
- ⚠️ 四、C++ 关键代码实现
- 🐛 五、调试实战：踩坑与修复（返回值核心问题）
- 📈 六、复杂度分析
- ✅ 七、总结与技巧提炼
链表作为数据结构的基础考点，K 个一组翻转链表是进阶高频题型，它完美融合了「单组链表翻转」与「分段处理」的核心思想。本文将严格围绕reverse N 实现思路，从问题定义、算法原理、代码实现到调试踩坑，逐帧拆解这道经典题，带你彻底吃透链表分段翻转的底层逻辑！
视频地址
因为想更好的为大佬服务，制作了同步视频，这是Bilibili的视频地址
🔍 一、问题核心含义：K 个一组翻转链表
1. 官方定义（严格版）
以 k 个节点为一个分组，对链表的每一组进行完整反转；若链表剩余节点数量不足 k 个，则保持原有顺序不翻转。
2. 直观示例
输入链表：1 -> 2 -> 3 -> 4 -> 5，k = 3
- 第一组：
1、2、3（满足 3 个节点）→ 翻转 →3 -> 2 -> 1 - 第二组：
4、5（不足 3 个节点）→ 不翻转 - 最终输出：
3 -> 2 -> 1 -> 4 -> 5
3. 可视化流程图（Mermaid）
原链表: 1->2->3->4->5
分组 k=3
第一组: 1,2,3
第二组: 4,5
翻转后: 3->2->1
不翻转: 4->5
最终链表: 3->2->1->4->5
图表说明：清晰展示了「分组→判断长度→分组翻转→拼接结果」的全流程，不足 k 个的分组直接保留原序。
📊 二、算法原理：基于「reverse N」的分层实现
本题的核心解题思路是拆分法：将「K 组翻转」拆解为两个基础能力的组合——
- reverse N 计数判断：检查当前链表是否有足够的 N 个节点供翻转；
- __reverse N 私有翻转：真正实现「翻转链表前 N 个节点」的核心逻辑。
这是官方推荐的最优解思路，无冗余操作，时间复杂度趋近于 O(n)。
1. 基础能力：reverse N 节点计数判断
作用：前置校验，避免对不足 k 个节点的分组执行翻转。
实现逻辑：
- 定义指针
p指向当前分组的头节点； - 循环递减 k，同时让
p向后遍历； - 若循环结束后
p不为空 → 剩余节点 ≥k，可翻转； - 若
p为空 → 剩余节点 <k，终止翻转。
2. 核心能力：__reverse N 前 N 个节点翻转
这是真正执行翻转的私有函数，严格遵循题目指定逻辑：
- 递归终止条件：
n == 1，直接返回当前头节点（最后一个节点是新头）； - 定义
tail：指向head->next（原分组头节点，翻转后成为分组尾节点）； - 定义
newHead：递归翻转后的新头节点； - 最终返回
newHead（翻转后分组的头节点）。
💡 三、整体实现框架：虚拟头节点 + 双指针循环
链表翻转的最大坑点是头节点会变化，因此必须使用虚拟头节点技巧破局；同时通过双指针记录关键位置，保证分组拼接不断裂。
1. 核心技巧：虚拟头节点
创建一个虚拟节点 dummy，让 dummy->next = 原链表头节点。
作用：无论链表头节点如何翻转，最终直接返回 dummy->next 即可，彻底解决头节点边界问题。
2. 关键位置指针定义
我们定义两个核心指针，这是循环翻转的关键：
| 指针名称 | 核心作用 | 位置变化 |
|---|---|---|
p | 待翻转区域的前驱节点 | 始终指向当前分组的前一个节点，初始指向虚拟头 |
q | 待翻转区域的头节点 / 翻转后的尾节点 | 初始 = p->next，翻转后成为当前分组的尾节点，是下一次的 p |
3. 循环翻转逻辑
- 以
reverseN(q, k)为循环条件（返回非空说明可翻转）； - 执行翻转，将前驱节点
p与新头节点拼接； - 指针后移：
p = q（当前分组尾 → 下一组前驱），q = p->next（下一组头）； - 直到
reverseN返回空，循环结束。
⚠️ 四、C++ 关键代码实现
以下是精简核心版代码，仅保留性能关键逻辑，注释全覆盖核心步骤：
#include <iostream> using namespace std; // 链表节点定义 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: // ===================== 核心1：翻转前n个节点（__reverseN）===================== ListNode* __reverseN(ListNode* head, int n) { // 终止条件：n=1，返回当前头（翻转后新头） if (n == 1) return head; // tail：原分组头，翻转后是分组尾节点 ListNode* tail = head->next; // 递归翻转剩余n-1个节点 ListNode* newHead = __reverseN(head->next, n-1); // 拼接节点：尾节点指向当前头 tail->next = head; head->next = nullptr; return newHead; } // ===================== 核心2：判断是否有n个节点（reverseN判断）===================== ListNode* hasNNode(ListNode* head, int n) { ListNode* p = head; // 向后数n个节点 while (n-- && p) { p = p->next; } // p非空=有n个节点，返回p；空=不足n个，返回nullptr return p; } // ===================== 主函数：K个一组翻转 ===================== ListNode* reverseKGroup(ListNode* head, int k) { // 虚拟头节点（解决头节点翻转边界） ListNode* dummy = new ListNode(-1); dummy->next = head; // p：待翻转区前驱；q：待翻转区头节点 ListNode* p = dummy; ListNode* q = p->next; // 循环：有k个节点则翻转，否则终止 while (hasNNode(q, k)) { // 翻转q开头的k个节点，得到新头 ListNode* newHead = __reverseN(q, k); // 前驱节点拼接新头 p->next = newHead; // 指针后移：p=当前分组尾，q=下一组头 p = q; q = p->next; } // 返回最终链表头（虚拟头的next） return dummy->next; } }; 🐛 五、调试实战：踩坑与修复（返回值核心问题）
在编写代码时，返回值错误是最常见的bug，结合题目要求复盘调试过程：
1. 初始错误
✅ 问题：最初直接返回 head（原链表头节点），导致结果错乱；
✅ 原因：分组翻转后，原链表头节点变成了第一组的尾节点，不再是整个链表的头。
2. 修复方案
返回虚拟头节点的next：return dummy->next，无论头节点如何翻转，虚拟头始终指向链表真正的头。
3. 翻转判断逻辑
题目指定关键判断：
if (p->next != q) → 说明发生了翻转；
if (p->next == q) → 说明未翻转（不足k个节点）。
该判断用于验证分组是否成功翻转，是调试的核心依据。
📈 六、复杂度分析
- 时间复杂度：O(n)
每个节点仅被遍历一次（计数一次 + 翻转一次），无嵌套循环；
- 空间复杂度：O(k)
递归调用栈深度为 k（分组长度），若改用迭代版 __reverseN，空间可优化为 O(1)。
✅ 七、总结与技巧提炼
- 核心思想：大问题拆小 → 用
reverseN做计数校验，__reverseN做单组翻转； - 必用技巧：虚拟头节点解决链表头变化的边界问题；
- 指针关键：
p记录前驱，q记录分组头尾，保证链表不断裂； - 终止条件：剩余节点不足 k 个时，直接终止循环，不做任何操作。
这道题是链表递归+迭代的综合运用，吃透「reverse N」思路，所有链表分段翻转类题目都能迎刃而解！
