LeetCode 92 区间反转：递归与哨兵节点实战解析

代码关键解析：

• tail 保存了当前节点的直接后继，是回溯时调整指针的核心；
• 递归会一直深入到待反转的最后一个节点，回溯时从后往前调整指针，完美实现反转；
• 未反转的节点完全不影响，保证了链表的完整性。

实战攻坚：LeetCode 92 链表区间反转

1. 题目问题描述

LeetCode 92. 反转链表 II：给你单链表的头指针 head 和两个整数 m、n（1 ≤ m ≤ n ≤ 链表长度），请你反转从位置 m 到位置 n 的链表节点，返回反转后的链表。

2. 神器加持：虚拟头节点（哨兵）技巧

这是链表题中解决边界问题的万能技巧！

• 定义：创建一个额外的链表节点（值任意，如 0），让它的 next 指向原链表的头节点，这个节点就是虚拟头节点（dummy）；
• 核心作用：消除「待反转区间包含原链表头节点」的特殊情况，统一所有操作逻辑。

我们用文字描述虚拟头节点的结构：虚拟头节点 dummy 独立于原链表，指针 p 只需移动 m-1 步，就能精准定位到待反转区间的前驱节点，无论 m=1 还是 m>1，逻辑完全一致。

3. 整体解题思路

将区间反转问题拆解为 3 个简单步骤，完美复用我们的 reverseN 函数：

1. 定位前驱节点：通过虚拟头节点，移动指针找到第 m-1 个节点（记为 p），它是待反转区间的前一个节点；
2. 计算反转长度：待反转节点数 k = n - m + 1；
3. 调用工具函数 + 拼接：调用 reverseN 反转 p.next 开头的 k 个节点，将 p.next 指向反转后的新头节点，完成拼接。

4. 完整代码实现（C++）与逐行解析

// 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;
}

代码关键解析：

• 虚拟头节点彻底规避了 m=1 时头节点变化的边界问题；
• 仅通过一次循环定位前驱节点，时间复杂度极低；
• 核心反转逻辑完全复用 reverseN，代码复用性拉满。

5. 算法复杂度分析

• 时间复杂度：O(n)，仅遍历链表一次，递归操作也是线性的；
• 空间复杂度：O(n)，递归调用会占用栈空间（若改用迭代实现 reverseN，空间可优化为 O(1)）。

算法原理深度剖析

1. 递归反转的核心原理

链表递归反转的本质是后序遍历：先递归深入到子问题的终止节点，再回溯调整指针。对于 reverseN，我们把「反转前 n 个节点」分解为「反转前 n-1 个节点」的子问题，直到 n=1 到达终点，再逐层回溯调整指针，最终完成整体反转。

2. 虚拟头节点的底层逻辑

普通链表操作中，头节点没有前驱，当反转区间包含头节点时，需要单独写判断逻辑。虚拟头节点为原链表增加了一个「公共前驱」，让所有节点的操作逻辑完全统一，代码更简洁、更健壮。

算法学习核心建议

结合本题的学习，分享一些算法刷题的核心方法论：

1. 思维与代码双管齐下：学习算法分为学思路和写代码两个过程，缺一不可。先理解递归分解、区间拆解的思维逻辑，再动手敲代码，才能真正内化；
2. 基础工具优先掌握：复杂算法题都是基础工具的组合，比如本题的 reverseN 就是核心工具，吃透基础，进阶题迎刃而解；
3. 实操大于空想：不要只看题解，跟着思路逐行敲代码，调试指针操作，才能攻克链表的指针难点；
4. 刻意练习边界情况：链表题的坑点都在边界（如 m=1、n=链表长度），刻意针对边界测试，提升代码健壮性。

总结

LeetCode 92 区间反转，是链表递归反转的里程碑式题目。它教会我们：复杂问题拆解为基础子问题，用工具函数简化核心逻辑，用技巧规避边界问题。从反转前 n 个节点，到区间反转，不仅是代码的进阶，更是递归思维的升华。希望大家通过本文，彻底吃透链表反转的核心，在算法刷题的路上稳步前行！