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

# 我的实现是直接用BM1的反转链表，先找到m和n对应节点，把（m,n）的链表先反转，再连接合并上，
class ListNode:  
    def __init__(self, x):  
        self.val = x  
        self.next = None  
 
def reverseList(head):  
    prev = None  
    current = head  
    while current:  
        next_node = current.next  # 保存下一个节点  
        current.next = prev  # 反转当前节点的指针  
        prev = current  # 将prev移动到当前节点  
        current = next_node  # 将current移动到下一个节点  
    return prev          
    
def getnumnext(head: ListNode, num):
    current = head
    while num-1:
        if current.next == None:
            return None
        current = current.next
        num -= 1
    return current
  
def reverseBetween(head: ListNode, m: int, n: int) -> ListNode:
    current = getnumnext(head, m)
    if m > 1:
        pre = getnumnext(head, m-1)
    else:
        pre = ListNode(0) 
    post = getnumnext(head, n+1)
    getnumnext(current,n-m+1).next = None
    newnode = reverseList(current)
    pre.next = newnode
    getnumnext(newnode, n-m+1).next = post
    return head
    

head = ListNode(1)  
# head.next = ListNode(2)  
# head.next.next = ListNode(3)  
# head.next.next.next = ListNode(4)  
# head.next.next.next.next = ListNode(5)  

new_head = reverseBetween(head, 1, 1)
            
# 打印反转后的链表  
while new_head:  
    print(new_head.val, end=" -> ")  
    new_head = new_head.next