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

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @param m int整型 
# @param n int整型 
# @return ListNode类
#
"""
 解题思路总结：
 1.定义一个虚拟头结点res 指向head 
 2. 定义left 指针从res 开始 移动到 m 位置前一个位置，移动m-1 次
3. 定义 right 从left 位置继续移动n-m+1 次到达【m,n】区间末尾节点
4. tail =right.next 保存尾部
5. 切断链表  ： leftNode 保存【m,n】 区间左端点，前一个的next指向None ,即left.next=None
  n位置right 的next 指向空 ，right.next=None  
6. 将切出来的【n,m】区间的头节点 leftNode 传入reverse(leftNode) 反转这段链表

7. 将链表拼接起来 left.next=reverse(leftNode)  原来的lefteNode 反转之之后变成中间部分的尾部指向 tail:
   leftNode.next=tail   
8.返回虚拟节点的next :res.next
"""


class Solution:
    def reverseBetween(self , head: ListNode, m: int, n: int) -> ListNode:
        # write code here
        # 定义一个链表反转
        def reverse( head:ListNode)->ListNode:
            
            if not head or not head.next:  # 一个节点或者空节点
                print(head.val)
                return head 
            cur =head
            pre=None
            while cur:
                next=cur.next 
                cur.next=pre 
                pre=cur
                cur =next
            return pre 
        if not  head or not head.next:
            return head
        if  m>=n:
            return head
        # left 遍历到 m-1 位置
        # 定义虚拟节点
        res=ListNode(-1)
        res.next=head
        left  =res
        k=m 
        while  k-1 >0: #移动到 left 前一个节点
            left=left.next
            k-=1
        right =left # 从left 开始走 n-m+1
        k=n-m+1  # 移动区间右端点
        while k>0:
            
            right=right.next
            k-=1
        #

        # if left==right: # 不需要反转
        #     return head
        # 保存 right 后一个节点 保存尾部
        # 切断
        #print("right",left.val,right.val)
        leftNode=left.next
        left.next=None
        tail=right.next  # 保存尾部
        right.next=None
        # 反转中间
        #print('mid',mid.val,right_next.val)
        new_mid=reverse(leftNode)
        left.next=new_mid

        
        # new_tail = new_mid
        # while new_tail.next:
        #     new_tail=new_tail.next
        leftNode.next=tail  # 原来的m 变成中间的尾部直接指向尾部
        #print("tail",tail.val)
        # 拼接尾部    
    
        
        return res.next