反转链表中的指定区间

题目

反转链表中的指定区间

信息

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

考点

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

快速回答

反转链表指定区间的核心步骤：

1. 定位区间前驱节点和区间尾节点
2. 切断区间子链表
3. 反转子链表
4. 重新连接链表

注意事项：

• 处理头节点可能被反转的情况
• 正确处理指针指向关系
• 处理区间等于整个链表的情况

问题描述

给定单链表头节点，反转从位置 left 到位置 right 的链表节点（位置从1开始计数），要求空间复杂度 O(1)，时间复杂度 O(n)。

示例：
输入：1→2→3→4→5, left=2, right=4
输出：1→4→3→2→5

原理说明

核心思路分为四步：

1. 定位关键节点：找到 left 前驱节点(pre)和 right 节点(end)
2. 切断子链表：保存 end.next 后断开子链表
3. 反转子链表：反转从 left 到 right 的子链表
4. 重新连接：将 pre.next 指向反转后的新头，原 left 节点指向 end.next

代码示例（Python）

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

def reverseBetween(head, left, right):
    # 处理空链表或单节点
    if not head or left == right:
        return head

    # 创建哑节点处理头节点变化
    dummy = ListNode(0)
    dummy.next = head
    pre = dummy

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

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

    # 切断子链表
    start = pre.next
    next_node = end.next
    end.next = None

    # 反转子链表
    prev, curr = None, start
    while curr:
        temp = curr.next
        curr.next = prev
        prev = curr
        curr = temp

    # 重新连接
    pre.next = prev
    start.next = next_node

    return dummy.next

最佳实践

• 使用哑节点(dummy node)统一处理头节点变化
• 先移动指针定位再操作，避免指针丢失
• 反转完成后立即断开原链接，防止循环链表
• 添加边界检查：left=1 或 right=链表长度

常见错误

• 未处理 left=1 时头节点变化
• 反转后未正确连接前后片段（造成断链）
• 移动指针次数错误（应移动 right-left+1 次）
• 未保存断链后的下一个节点导致数据丢失
• 尝试直接交换值（违反链表操作原则）

扩展知识

• 递归反转：可递归实现子链表反转，但空间复杂度 O(n)
• K个一组反转：本题变种，每 k 个节点反转一次
• 双向链表：双向链表反转更简单，但需额外处理 prev 指针
• 复杂度优化：一次遍历解法（定位同时反转）