LeetCode 92. Reverse Linked List II 题解

LeetCode 92. Reverse Linked List II 题解题目描述给你单链表的头指针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]解题思路方法穿针引线法思路首先找到反转部分的前一个节点pre以及反转部分的第一个节点start然后反转从left到right的链表节点最后将反转后的链表与原链表连接起来复杂度分析时间复杂度O(n)其中 n 是链表的长度。需要遍历链表一次。空间复杂度O(1)只需要常数级的额外空间。代码实现方法穿针引线法# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def reverseBetween(self, head: Optional[ListNode], left: int, right: int) - Optional[ListNode]: # 创建哑节点方便处理头节点的情况 dummy ListNode(0) dummy.next head # 找到反转部分的前一个节点 pre pre dummy for _ in range(left - 1): pre pre.next # 反转部分的第一个节点 start start pre.next # 当前需要反转的节点 current current start.next # 反转从 left 到 right 的链表节点 for _ in range(right - left): # 保存下一个需要反转的节点 next_node current.next # 反转当前节点 current.next pre.next # 更新 pre.next pre.next current # 移动 current 到下一个节点 current next_node # 将反转部分的最后一个节点与原链表连接起来 start.next current return dummy.next测试用例测试用例 1输入head [1,2,3,4,5], left 2, right 4输出[1,4,3,2,5]测试用例 2输入head [5], left 1, right 1输出[5]测试用例 3输入head [1,2,3,4,5], left 1, right 5输出[5,4,3,2,1]总结本题是链表的经典问题主要考察对链表操作的理解和应用。通过使用穿针引线法我们可以高效地反转链表的指定部分。穿针引线法的核心思想是找到反转部分的前一个节点然后逐个反转链表节点最后将反转后的链表与原链表连接起来。这种方法不仅适用于反转链表 II 问题还可以应用于许多其他需要操作链表指定部分的场景。掌握链表操作的技巧对于解决这类问题非常重要。