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

idea是非常简单的

我们先找到反转前的第一个节点:before_start ,然后从第一个节点开始反转。

反转结束后将before_start的下一个节点指向反转结束后紧跟着的那个节点。

并将before_start指向需要反转的尾节点。

因为m=1的时候，before_start应该在head之前，所以不妨设计一个哑节点来指向链表的头。

同时，在反转结束后，head指向的节点也不是链表的头部，所以这时要返回before_start.next，因为before_start.next被设置为指向反转的尾节点，这尾节点就是现在的链表的头。

 class Solution:
def reverseBetween(self , head: ListNode, m: int, n: int) -> ListNode:
    # write code here
    if head ==None or head.next == None or n-m==0:
        return head

    pre=None
    before_start = ListNode(0)
    before_start.next = head
    for i in range(0,m-1):
        before_start = before_start.next    #记录反转前的那个      
    cur = before_start.next  #需要反转的第一个
    for _ in range(n-m+1):
        tmp = cur.next
        cur.next = pre
        pre = cur
        cur = tmp
        
    before_start.next.next = cur  #开始的节点指向反转范围之后的那一点
    before_start.next = pre       #开始之间的节点指向反转范围的最后一点
    if m==1:
        return before_start.next  #m=1时需要用before_start.next来找第一个节点
    return head