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

# 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 m==n or head ==None or head.next ==None:
            return head

        res = ListNode(-1)  #加表头，最终返回res.next
        res.next = head

        prev = res  #m前一个元素, 每次遍历只改变next指针，指向上次遍历p的下一跳
        p = head    #遍历指针,每次向前移动一位，到n后停止

        for _ in range(m-1): #找到m位置
            prev = p
            p = p.next

        for _ in range(m,n):
            temp = p.next   #保存当前p的下一跳
            p.next = temp.next  #p的下一跳变为原来下一跳的下一跳
            temp.next = prev.next   #原来p的下一跳（temp）指向p自己，实现反转
            prev.next = temp    #  prev的指针刷新为原先p的下一跳
        
        return res.next
'''
假设列表1~5，m=2,n=4,找到m后
prev:  1  ==>prev.next: 2 ==> prev.next.next: 3 ==> prev.next.next.next: 4
p:  2 p.next: 3

while遍历过程中
prev:  1  ==>prev.next: 3 ==> prev.next.next: 2 ==> prev.next.next，next: 4
p:  2 p.next: 4
while遍历过程中
prev:  1  ==>prev.next: 4 ==> prev.next.next: 3 ==> prev.next.next，next: 2
p:  2 p.next: 5
'''