python-leetcode-反转链表 II

92. 反转链表 II - 力扣（LeetCode）

# 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: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        # 如果链表为空，或者不需要反转，直接返回
        if not head or left == right:
            return head

        # 创建虚拟头节点，以简化操作（处理 left 为 1 的情况）
        dummy = ListNode(0)
        dummy.next = head
        prev = dummy

        # 1. 找到 left 节点的前一个节点
        for _ in range(left - 1):
            prev = prev.next

        # 2. 开始反转
        curr = prev.next  # left 节点
        next_node = None  # 用于存储临时的下一个节点
        for _ in range(right - left + 1):
            next_temp = curr.next
            curr.next = next_node
            next_node = curr
            curr = next_temp

        # 3. 连接反转后的部分
        prev.next.next = curr  # 连接到 right 节点后的部分
        prev.next = next_node  # 连接反转部分的头节点

        return dummy.next