【牛客157题】：反转链表指定区间（虚拟头节点解法）
5个月前 (07-06)
一、题目解读
牛客第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题解
原创内容 转载请注明出处
