【牛客157题】：反转链表指定区间（虚拟头节点解法）

一、题目解读

牛客第157题要求反转链表中第m到n个节点（包含m和n）的区间，并保持其他节点顺序不变。例如，给定链表1→2→3→4→5，m=2，n=4，应返回1→4→3→2→5。题目重点在于处理边界条件（如m=1或n为末尾节点）及高效反转指定区间。

二、解题思路

用户代码采用“虚拟头节点+双指针迭代”策略：

1. 创建虚拟头节点dummy，指向原链表头head，简化边界处理（避免单独讨论m=1的情况）。

2. 分两步操作：

    Step1：通过指针pre定位到m-1节点，作为反转区间的起始点前驱。

    Step2：利用cur指针遍历m到n区间，通过临时变量tmp交换后续节点指针，实现局部反转。

3. 时间复杂度O(n)，空间复杂度O(1)，核心在于通过临时指针规避复杂指针操作。

三、解题步骤

1. 初始化：构建虚拟头节点dummy，并让pre指向它。

2. 定位前驱：通过for循环移动pre至m-1位置，确保后续反转的起点正确。

3. 区间反转：

    设置cur=pre.next（即m位置节点）。

    迭代n-m次，每次通过tmp暂存cur.next，将cur.next指向tmp.next（断开原链接），再将tmp插入pre与cur之间，完成局部反转。

4. 返回结果：最终head变为dummy.next（即原head或反转后的新头节点）。

四、代码与注释

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode dummy(-1); // 虚拟头节点简化边界处理
        dummy.next = head;
        ListNode *pre = &dummy; // pre指向虚拟头节点
        
        // Step1: 定位到m-1位置
        for (int i = 1; i < m; ++i) {
            pre = pre->next;
        }
        
        // Step2: 反转m到n区间
        ListNode *cur = pre->next; // cur从m位置开始
        for (int i = m; i < n; ++i) {
            ListNode *tmp = cur->next; // 暂存后续节点
            cur->next = tmp->next; // 切断cur与后续链接
            tmp->next = pre->next; // 将tmp插入pre与cur之间
            pre->next = tmp; // 更新pre.next指向反转后的节点
        }
        
        return dummy.next; // 返回结果链表头
    }
};

五、总结

本解法巧妙利用虚拟头节点统一边界逻辑，通过双指针迭代实现区间反转。关键点在于：

1. 虚拟头节点避免对m=1的特殊处理，使代码更简洁。

2. 反转过程通过临时指针暂存与交换，确保指针操作正确性。

3. 时间复杂度线性，适用于大规模链表场景。

掌握该思路能有效应对链表区间操作类题目。

参考：牛客157题解