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

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @param m int整型 
# @param n int整型 
# @return ListNode类
#
#   时间复杂度O(n), 空间复杂度O(1)
class Solution:
    def reverseBetween(self , head: ListNode, m: int, n: int) -> ListNode:
        # write code here
        if not head:
            return head
        else:
            root, index = head, 0
            #   m, n位置的节点
            m_node, n_node = None, None
            #   m-1, n+1位置的节点
            start, end = None, None
            #   临时节点
            p, q = None, None
            while head:
                index += 1
                if m <= index and index <= n:
                    #   逆转链表
                    if m != n:
                        if index == m:
                            p = head
                            m_node = head
                            head = head.next
                        else:
                            q = head.next
                            head.next = p
                            if index == n:
                                n_node = head
                                n_node.next = p
                            p = head
                            head = q
                    else:
                        #   处理特殊的m=n的情况，即无需逆转
                        m_node = head
                        n_node = head
                        head = head.next
                elif index == m - 1:
                    #   划定起始节点，即记录m-1的位置
                    start = head
                    head = head.next
                elif index == n + 1:
                    #   划定结束节点，即记录n+1的位置
                    end = head
                    head = head.next
                else:
                    #   向后遍历
                    head = head.next
            
            #   串联链表
            if n == index:
                m_node.next = None
            else:
                m_node.next = end
            if m == 1:
                root = n_node
            else:
                start.next = n_node
                
            return root