C++算法
LeetCode 92 链表区间反转：递归反转与哨兵技巧详解
LeetCode 92 区间反转问题要求反转链表中指定区间的节点。解决方案基于递归反转前 n 个节点的基础函数 reverseN，结合虚拟头节点（哨兵）技巧处理边界情况。通过定位前驱节点、计算反转长度并调用工具函数完成拼接。时间复杂度 O(n)，空间复杂度 O(n)。该方法将复杂问题拆解为基础子问题，利用递归后序遍历调整指针，有效规避了头节点变化的边界问题。
LeetCode 92 区间反转问题要求反转链表中指定区间的节点。解决方案基于递归反转前 n 个节点的基础函数 reverseN，结合虚拟头节点（哨兵）技巧处理边界情况。通过定位前驱节点、计算反转长度并调用工具函数完成拼接。时间复杂度 O(n)，空间复杂度 O(n)。该方法将复杂问题拆解为基础子问题，利用递归后序遍历调整指针，有效规避了头节点变化的边界问题。
链表反转是数据结构与算法中的经典高频考点，从基础的全链表反转，到反转前 n 个节点，再到进阶的区间反转，层层递进。本文将以 LeetCode 92. 反转链表 II 为核心，从基础的「反转前 n 个节点」递归实现讲起，结合虚拟头节点神器，手把手拆解区间反转的解题逻辑，带你彻底掌握链表递归反转的核心思想！
链表是一种线性、离散存储的数据结构，节点之间通过指针关联，无法像数组一样随机访问，这也让链表反转成为了考察指针操作与递归思维的最佳题型。
LeetCode 92 区间反转问题，并非孤立的算法题，而是「反转前 n 个节点」的进阶应用。我们的解题思路非常清晰：先攻克基础的前 n 节点反转，再将区间反转问题拆解为基础问题的组合，化繁为简，轻松破解难题。
在解决区间反转之前，我们必须先实现一个核心工具函数：反转链表的前 n 个节点，这是解题的核心基石。
我们定义递归函数 reverseN，功能如下：
递归的核心是分解子问题 + 终止条件 + 回溯调整指针，严格遵循以下逻辑：
我们以链表 1->2->3->4 为例，通过表格直观展示函数效果：
| 原链表结构 | 输入参数 n | 反转后链表结构 |
|---|---|---|
| 1->2->3->4 | 2 | 2->1->3->4 |
| 1->2->3->4 | 3 | 3->2->1->4 |
// 链表节点定义（通用）
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) {}
};
// 核心函数：反转链表前 n 个节点（递归实现）
ListNode* reverseN(ListNode* head, int n) {
// 终止条件：n=1，到达待反转的最后一个节点，直接返回
if (n == 1) {
return head;
}
// 记录当前节点的下一个节点（待反转的子链表头）
ListNode* tail = head->next;
// 递归反转：反转 head.next 的前 n-1 个节点，得到新头节点
ListNode* newHead = reverseN(head->next, n - 1);
// 指针调整：当前头节点指向 tail 的后继节点
head->next = tail->next;
// tail 指向当前头节点，完成局部反转
tail->next = head;
// 返回反转后的新头节点
return newHead;
}
✅ 代码关键解析：
LeetCode 92. 反转链表 II：
给你单链表的头指针 head 和两个整数 m、n（1 ≤ m ≤ n ≤ 链表长度），请你反转从位置 m 到位置 n 的链表节点，返回反转后的链表。
这是链表题中解决边界问题的万能技巧！
📌 图表说明：虚拟头节点独立于原链表，指针 p 只需移动 m-1 步，就能精准定位到待反转区间的前驱节点，无论 m=1 还是 m>1，逻辑完全一致。
将区间反转问题拆解为 3 个简单步骤，完美复用我们的 reverseN 函数：
// LeetCode92 区间反转主函数
ListNode* reverseBetween(ListNode* head, int m, int n) {
// 1. 创建虚拟头节点，指向原链表头
ListNode* dummy = new ListNode(0);
dummy->next = head;
// 2. 定义指针 p，初始指向虚拟头节点
ListNode* p = dummy;
// 3. 移动 m-1 步，定位到待反转区间的前驱节点
for (int i = 0; i < m - 1; i++) {
p = p->next;
}
// 4. 计算需要反转的节点个数
int k = n - m + 1;
// 5. 调用 reverseN，反转 p.next 开头的 k 个节点
p->next = reverseN(p->next, k);
// 6. 返回虚拟头节点的 next（最终链表头）
return dummy->next;
}
✅ 代码关键解析：
链表递归反转的本质是后序遍历：先递归深入到子问题的终止节点，再回溯调整指针。
对于 reverseN，我们把「反转前 n 个节点」分解为「反转前 n-1 个节点」的子问题，直到 n=1 到达终点，再逐层回溯调整指针，最终完成整体反转。
普通链表操作中，头节点没有前驱，当反转区间包含头节点时，需要单独写判断逻辑。虚拟头节点为原链表增加了一个「公共前驱」，让所有节点的操作逻辑完全统一，代码更简洁、更健壮。
结合本题的学习，给大家分享算法刷题的核心方法论：
LeetCode 92 区间反转，是链表递归反转的里程碑式题目。它教会我们：复杂问题拆解为基础子问题，用工具函数简化核心逻辑，用技巧规避边界问题。
从反转前 n 个节点，到区间反转，不仅是代码的进阶，更是递归思维的升华。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online