92. 反转链表 II

题目链接：92. 反转链表 II

题目描述

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

核心思考：头插法（原地局部反转）

这道题是链表反转的进阶版。最容易想到的朴素做法是：找到需要反转的区间，把这部分单独截取出来，按常规方法反转，然后再把头尾接回原链表。这种思路虽然直观，但需要多次遍历并小心翼翼地维护边界断点。

关联题目： 如果你想回顾标准的截取反转套路，可以去看看 234. 回文链表 里的第二步操作。

为了追求更优雅的 $O(N)$ 一次遍历，我们使用了头插法（穿针引线法）。核心优势在于可以在原地顺带完成反转。

1. 哑节点 (Dummy Node) 特判保护

反转的起始位置 left 有可能刚好是 1，也就是真正的头节点自身也参与反转。为了防止这种边界情况触发繁杂的 if-else 头节点变更逻辑，我们照例在最前面接上一个静态的 dummy 虚拟节点。

2. 穿针引线

整个头插法的精髓在于，在到达反转区间后，我们严格固定两个静态的参照指针：

• pre 指针：永远停留在反转区间之前的那个节点，作为插入的“抛锚点”。
• curr 指针：永远指向反转区间内部最初身处队首的那个节点（随着反转的进行，它最终会被推到区间的队尾）。

在随后的每一次交换循环中，我们只做一套动作：

1. 锁定紧接在 curr 后面的那个节点 nxt。
2. 将这个 nxt 节点“拎”出来，跨越其他节点，直接强行插入到整个区间的前排（也就是 pre 的正后方）。
3. 如此循环往复进行 right - left 轮，原本在后面的节点就逐个排到了前面，反转自然完成。

解题思路 (Python)

class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        if not head or left == right:
            return head
        # 引入 Dummy 节点以处理 left=1 的情况
        dummy = ListNode(0)
        dummy.next = head
        pre = dummy
        
        # 将 pre 移动到待反转区间的前驱位置
        for i in range(left-1):
            pre = pre.next
        curr = pre.next 
        
        # 执行 (right - left) 次交换
        for _ in range(right - left):
            # 暂存待移动的节点
            nxt = curr.next
            
            # 拎起并插入
            # 1. 让 curr 跳过 nxt 
            # 2. 让 nxt 指向当前的区间头部 
            # 3. 让 pre 指向新的区间头部 
            # 2->3->4
            # 3->2->4
            # 4->3->2
            curr.next = nxt.next
            nxt.next = pre.next
            pre.next = nxt
            
        return dummy.next

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是链表总节点数。定位到反转起点加上执行反转交互，整个过程绝对不会超过单次扫视链表的遍历时间跨度，属严格的线性耗时。
• 空间复杂度：$O(1)$。一切都是在原节点上进行指针变更接驳，仅利用了常量级的额外游标指针辅助存储，空间极其省流。