企业官网建设流程全解析

LeetCode 92. 反转链表 II｜Python 解法详解

CSDN 算法专题 · 链表 | 难度：中等

题目信息

• 题号：92
• 难度：中等
• LeetCode：题目链接

题目描述

给定单链表和位置 left、right，原地反转从 left 到 right 的节点并返回头节点。

示例

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

约束

1 ≤ left ≤ right ≤ 链表长度。

解题思路

核心观察

用哑节点处理 left=1。先找到反转区间前驱 prev，再反复把 current 后面的节点摘下并插到 prev 后面，即头插法完成局部反转。

推导与执行步骤

1. 建立 dummy 并定位区间前驱
2. 令 current 指向区间首节点
3. 摘下 current.next
4. 把摘下节点插到 prev 后，重复 right-left 次

为什么这个方法正确

算法始终围绕上述核心观察维护有效状态，并且每一步只排除已经能够证明不可能产生更优答案的情况。按照执行步骤处理后，所有可能影响答案的元素或节点都会被恰好检查，因此不会遗漏合法答案；状态更新又严格遵守题目约束，所以最终结果有效。

从边界看，空区间、单个元素、全部相同或完全不匹配等情况都会落入初始化条件或循环终止条件，不需要依赖未定义状态。实现时再重点检查下标、空节点和重复元素，即可保证算法在极端输入下仍然成立。

Python 代码

# 解法核心：用哑节点处理 left=1。先找到反转区间前驱 prev，再反复把 current 后面的节点摘下并插到 prev 后面，即头插法完成局部反转。# 实现步骤：# 1. 建立 dummy 并定位区间前驱# 2. 令 current 指向区间首节点# 3. 摘下 current.next# 4. 把摘下节点插到 prev 后，重复 right-left 次fromtypingimportOptionalclassListNode:def__init__(self,val=0,next=None):self.val=val self.next=nextclassSolution:defreverseBetween(self,head:Optional[ListNode],left:int,right:int)->Optional[ListNode]:ifnothead:returnNonedummy=ListNode(0)# 哑节点用于统一处理头节点可能变化的情况dummy.next=head prev=dummy# 保存当前节点的前驱节点for_inrange(left-1):prev=prev.next# 保存当前节点的前驱节点current=prev.next# 指向当前正在处理的节点或元素for_inrange(right-left):next_node=current.nextcurrent.next=next_node.nextnext_node.next=prev.nextprev.next=next_nodereturndummy.next

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

易错点

需要同时维护区间前后的连接，哑节点能消除头节点特判。

总结

这道题的关键是：用哑节点处理 left=1。理解这一点后，再结合边界条件检查，代码就能保持清晰且稳定。