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

这段代码里，newHead 是最终整个反转段的新头，而 head 变成了反转段的尾。理解这个指针流向，递归就不难了。

实战：LeetCode 92 区间反转

题目要求反转从位置 m 到位置 n 的节点。这其实就是把刚才的工具函数复用起来，但多了个边界处理的坑。

1. 难点：边界情况

如果 m = 1，意味着要反转的部分包含原链表的头节点。这时候头节点会变，返回值不再是原来的 head。如果每次都要单独判断 m=1，代码会显得臃肿且容易出错。

2. 神器：虚拟头节点（哨兵）

解决这个问题的万能技巧是引入虚拟头节点（dummy）。创建一个额外节点，让它的 next 指向原链表头。这样无论 m 是多少，待反转区间的前驱节点永远存在，逻辑完全统一。

想象一下，指针 p 从 dummy 开始移动 m-1 步，就能精准定位到待反转区间的前一个节点。不需要关心 m 是不是 1，因为 dummy 永远在那里。

3. 完整解题思路

1. 创建哨兵：dummy->next = head。
2. 定位前驱：移动指针找到第 m-1 个节点，记为 p。
3. 计算长度：需要反转的节点数 k = n - m + 1。
4. 调用工具：调用 reverseN(p.next, k)，并将结果接回 p。
5. 返回结果：返回 dummy->next。

4. 代码实现（C++）

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 个节点
    // 注意：reverseN 会修改 p.next 指向新的头，并更新内部指针
    p->next = reverseN(p->next, k);
    
    // 6. 返回虚拟头节点的 next（最终链表头）
    return dummy->next;
}

这里有个小陷阱：reverseN 内部修改了指针，所以 p->next 必须重新赋值，否则链表会在 p 处断开。实际调试时多画几次图，指针关系就清晰了。

复杂度分析

• 时间复杂度：O(n)。我们只遍历了一次链表，递归深度也是线性的。
• 空间复杂度：O(n)。主要是递归调用栈占用的空间。如果改用迭代实现 reverseN，空间可以优化到 O(1)，但递归写法更直观，适合理解原理。

总结

LeetCode 92 是链表递归反转的里程碑式题目。它教会我们两个核心点：

1. 复杂问题拆解：区间反转本质就是'定位 + 基础反转 + 拼接'。不要试图一次性写出所有逻辑，先写好 reverseN 这个小工具。
2. 边界处理技巧：虚拟头节点能消除大部分特殊情况的判断，让代码更健壮。

刷题时别光看题解，跟着思路逐行敲代码，调试指针操作，才能真正攻克链表的难点。