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

# 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:
        # write code here
        if not head or m == n:
        #如果链表为空（head is None），直接返回；
        #如果 m == n，说明不需要反转（只涉及一个节点），也直接返回原链表。
            return head

        dummy = ListNode(0)     #创建一个虚拟头结点
        dummy.next = head       #指向原链表头结点

        prev = dummy            
        #这样即使 m == 1（也就是需要从头节点开始反转），
        #我们也能统一用 prev.next 来操作，不需要单独处理头节点变化的特殊情况；

        # 1. 找到第 m-1 个节点
        for _ in range(m - 1):
            prev = prev.next

        # 2. 开始反转 m 到 n 的区间
        cur = prev.next          # 第 m 个节点
        reverse_tail = cur       # 反转后的尾节点（原头节点）
        prev_rev = None          # 反转后的头结点
        for _ in range(n - m + 1):  #反转
            nxt = cur.next       #保留原链表当前节点的下一个节点
            cur.next = prev_rev  #在新链表前插入节点(先插位置)
            prev_rev = cur       #新头节点赋值(再插值)
            cur = nxt            #恢复到原链表的下一个节点

        # 3. 重新连接
        prev.next = prev_rev     # prev_rev 是反转后的新头
        reverse_tail.next = cur  # cur 是 n+1 个节点

        return dummy.next