给你单链表的头指针 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]
# [92] 反转链表 II
#反转 left 到 right 部分以后,再拼接起来
# @lc code=start
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
def reverse_linked_list(head: ListNode):
# 也可以使用递归反转一个链表
pre = None
cur = head
while cur:
next = cur.next
cur.next = pre
pre = cur
cur = next
# 因为头节点有可能发生变化,使用虚拟头节点可以避免复杂的分类讨论
dummy_node = ListNode(-1)
dummy_node.next = head
pre = dummy_node
# 第 1 步:从虚拟头节点走 left - 1 步,来到 left 节点的前一个节点
# 建议写在 for 循环里,语义清晰
for _ in range(left - 1):
pre = pre.next
# 第 2 步:从 pre 再走 right - left + 1 步,来到 right 节点
right_node = pre
for _ in range(right - left + 1):
right_node = right_node.next
# 第 3 步:切断出一个子链表(截取链表)
left_node = pre.next
curr = right_node.next
# 注意:切断链接
pre.next = None
right_node.next = None
# 第 4 步:同第 206 题,反转链表的子区间
reverse_linked_list(left_node)
# 第 5 步:接回到原来的链表中
pre.next = right_node
left_node.next = curr
return dummy_node.next
# @lc code=end