题解 | 链表内指定区间反转

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @param m int整型 
# @param n int整型 
# @return ListNode类
# 抄的GPT 的
class Solution:
    def reverseBetween(self , head: ListNode, m: int, n: int) -> ListNode:
        # write code 
        # 特殊情况：空链表不需要翻转
        if  not head or m == n:
            return head
        # 建立哑结点，统一处理头结点被反转的情况
        dummy = ListNode(0)
        dummy.next = head

        # prev 执行第 m-1个结点（初始指向 dummy）
        prev = dummy
        for _ in range(m -1):
            prev = prev.next
            # 若prev 为 None，说明m越界
        # subTail 指向子区间的第一个节点（位置 m)
        subTail = prev.next # 反转后会成为该子区间的尾节点

        # 使用curr游标与prevNode 做就地反转
        curr = subTail
        prevNode = None

        #反转n-m +1 个节点
        for _ in range(n -m +1):
            nxt = curr.next
            curr.next = prevNode
            prevNode = curr
            curr = nxt
        # 重新连接三段 prev - reversedHead(prevNode)  ...reversedTail(subTail) --- curr
        prev.next = prevNode
        subTail.next = curr

        return dummy.next