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

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @param m int整型 
# @param n int整型 
# @return ListNode类
#
class Solution:
    def reverseBetween(self , head: ListNode, m: int, n: int) -> ListNode:
        # 创建一个哑节点，这可以帮助简化插入节点等操作，特别是在链表头部处理时
        dummy_head = ListNode(-1)
        # 将哑节点指向原链表的头部，这样我们就不会丢失头节点的引用
        dummy_head.next = head

        # 使用一个指针从哑节点开始遍历链表，直到达到翻转部分的前一个节点
        pointer = dummy_head
        for i in range(m-1):
            pointer = pointer.next

        # 'reverse_pre'将作为反转部分的前一个节点
        reverse_pre = pointer
        # 'reverse_tail'将是反转部分的第一个节点，翻转后将成为尾部
        reverse_tail = pointer.next

        # 'pre'将跟踪我们即将翻转的节点的前一个节点
        # 'cur'是当前要翻转的节点
        pre = pointer.next
        cur = pre.next

        # 进行翻转操作直到达到指定的位置n
        while m < n:
            # 'temp'用来暂存'cur'的下一个节点，因为翻转过程中会丢失原有的next引用
            temp = cur.next
            # 将'cur'的next指向'pre'来实现翻转
            cur.next = pre
            # 'pre'和'cur'都前进一个节点
            pre = cur
            cur = temp
            # 我们已经处理了一个节点，所以减少n
            m += 1
        
        # 经过上面的循环，翻转部分已经完成，现在将翻转部分前面的节点连接到翻转后的头部
        reverse_pre.next = pre
        # 将翻转部分后的尾部连接到剩余未翻转部分的头部
        reverse_tail.next = cur

        # 因为我们使用了哑节点，所以返回哑节点的next，即原链表的头部
        return dummy_head.next