题解 | #链表内指定区间反转|时间复杂度O('n')#

# 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:
        if m == n:
            return head
        
        # 定义空头结点，避免特殊判断
        top = ListNode(1001)

        # 定义开始反转之前的位置
        startPre = top
        startPre.next = head
        # 确定开始反转的位置、开始反转之前的位置
        idx1 = m
        while idx1 > 1 :
            startPre = startPre.next
            idx1 -= 1
        start = startPre.next

        # 开始反转
        pre = None
        cur = start
        idx2 = n - m + 1
        while idx2 > 0 :
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
            idx2 -= 1
            
        # 确定结束反转的位置、结束反转之后的位置
        end = pre
        endAfter = cur

        # 拼接三段链表（反转前、反转、反转后）
        start.next = endAfter
        startPre.next = end

        # 定义的空头结点的next就是真正的头结点
        return top.next