题解 | #链表内指定区间反转O(size*(n-m))#

# 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:

        # 定义空头节点，避免特殊逻辑
        top = ListNode(1001)
        top.next = head
        
        # 寻找开始反转节点start、开始反转节点前一个节点pre
        pre = top
        idx1 = 0
        while idx1 < m - 1:
            pre = pre.next
            idx1 += 1
        start = pre.next
        pre.next = None

        # 寻找结束反转节点end、结束反转后一个节点post
        end = start
        idx1 = 0
        while idx1 < n - m:
            end = end.next
            idx1 += 1
        post = end.next
        end.next = None

        # start-end之间的反转，返回反转后的[head , tail]
        reverseResult = self.reverse(start)   

        # 开始拼接三段
        pre.next = reverseResult[0]
        reverseResult[1].next = post

        return top.next   


        

    def reverse(self , head: ListNode) -> List:
        if head.next == None:
            return [head , head]
        nxtReverseResult = self.reverse(head.next)
        head.next = None
        nxtReverseResult[1].next = head
        return [nxtReverseResult[0] , head]