day131—链表—反转链表Ⅱ（区域反转）（LeetCode-92）

题目描述

给你单链表的头指针head和两个整数left和right，其中left <= right。请你反转从位置left到位置right的链表节点，返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5], left = 2, right = 4输出：[1,4,3,2,5]

示例 2：

输入：head = [5], left = 1, right = 1输出：[5]

提示：

• 链表中节点数目为n
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

解决方案：

这段代码的核心功能是反转单链表中指定区间 [left, right] 内的节点（比如原链表 1→2→3→4→5，left=2、right=4 时，反转后为 1→4→3→2→5），采用「迭代法 + 虚拟头节点」实现，时间复杂度O(n)、空间复杂度O(1)，是区间反转链表的经典解法。

核心逻辑

代码通过 “定位反转起点 + 局部反转 + 重新连接” 三步完成区间反转，核心是用虚拟头节点规避头节点反转的边界问题：

1. 虚拟头节点与定位前驱：创建虚拟头节点dx指向原链表头，先找到反转区间的前驱节点p0（即 left 位置的前一个节点），避免反转头节点时的空指针问题；
2. 局部区间反转：以p0->next为起点，用pre/cur/nxt三个指针，迭代反转 [left, right] 范围内的节点（反转逻辑和完整反转链表一致）；
3. 重新连接链表：反转完成后，将原反转起点的节点（现在是反转区间的尾节点）指向反转区间后的第一个节点cur，再将p0指向反转区间的新头节点pre，恢复链表完整性；
4. 返回结果：最终返回虚拟头节点的next（即新链表的头节点）。

总结

1. 核心思路：用虚拟头节点简化边界处理，先定位反转区间前驱，再局部反转，最后重新拼接链表；
2. 关键操作：反转后p0->next->next = cur和p0->next = pre是重新连接链表的核心，避免区间反转后链表断裂；
3. 效率特点：一次遍历完成定位 + 反转 + 拼接，时间O(n)、空间O(1)，是区间反转链表的最优解法。

函数源码：

/** * Definition for singly-linked list. * 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) {} * }; */ class Solution { public: ListNode* reverseBetween(ListNode* head, int left, int right) { ListNode dx(0,head); ListNode* p0=&dx; for(int i=0;i<left-1;i++){ p0=p0->next; }//到达反转区域的前一个结点:p0 ListNode* nxt=nullptr; ListNode* pre=nullptr; ListNode* cur=p0->next;//反转的起始节点：p0->next for(int i=0;i<right-left+1;i++){ nxt=cur->next; cur->next=pre; pre=cur; cur=nxt; } p0->next->next=cur; p0->next=pre; return dx.next; } };