反转链表 II

题目

反转链表 II

信息

• 类型：问答
• 难度：⭐⭐

考点

链表操作,指针操作,边界条件处理

快速回答

反转链表 II 要求反转链表中从位置 left 到 right 的部分。核心步骤：

• 创建虚拟头节点简化边界处理
• 定位 left 前驱节点和 right 后继节点
• 反转指定区间内的子链表
• 重新连接反转后的子链表到原链表

时间复杂度 O(n)，空间复杂度 O(1)。

解析

问题描述

给定单链表头节点 head 和两个整数 left、right（1 ≤ left ≤ right ≤ 链表长度），反转从位置 left 到 right 的链表节点，返回反转后的链表头节点。

原理说明

核心是通过指针操作实现局部反转：

1. 使用虚拟头节点（dummy node）处理 left=1 的边界情况
2. 定位 left 位置的前驱节点（pre_left）和 right 位置的后继节点（succ_right）
3. 切断子链表，反转 left 到 right 的节点
4. 将反转后的子链表重新接入原链表

代码示例（Python）

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseBetween(head, left, right):
    # 创建虚拟头节点
    dummy = ListNode(0, head)
    pre_left = dummy

    # 定位 left 前驱节点
    for _ in range(left - 1):
        pre_left = pre_left.next

    # 定位 right 节点
    right_node = pre_left
    for _ in range(right - left + 1):
        right_node = right_node.next

    # 切断子链表
    left_node = pre_left.next
    succ_right = right_node.next
    right_node.next = None  # 断开连接

    # 反转子链表
    prev, cur = None, left_node
    while cur:
        next_node = cur.next
        cur.next = prev
        prev = cur
        cur = next_node

    # 重新连接链表
    pre_left.next = prev  # pre_left 接新头
    left_node.next = succ_right  # 新尾接后继

    return dummy.next

最佳实践

• 虚拟头节点：避免单独处理 left=1 的情况
• 四指针法：pre_left（左前驱）、left_node（原子链表头）、right_node（原子链表尾）、succ_right（右后继）
• 反转前断开连接：将子链表与主链表分离后再反转，避免指针混乱
• 循环定位优化：通过单次遍历定位关键节点（时间复杂度 O(n)）

常见错误

• 边界处理缺失：未处理 left=1 或 right=链表长度的情况
• 指针丢失：反转过程中未保存 next 指针导致链表断裂
• 连接顺序错误：反转后未正确连接 pre_left 和 succ_right
• 反转节点计数错误：未反转指定区间内的所有节点
• 空间浪费：使用额外空间存储节点值而非原地操作

扩展知识

• 递归反转：可通过递归实现子链表反转（空间复杂度 O(n)）
• K 个一组反转：本题变种，每 k 个节点反转一次（LeetCode 25）
• 双向链表反转：若为双向链表需额外处理 prev 指针
• 环形链表检测：反转操作可能意外形成环，需注意指针操作
• 应用场景：文本编辑器撤销操作、浏览器历史记录管理等需要局部反转的场景