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

这个是排行榜上的解法，其亮点在于使用了“虚拟头节点”（res）避免了许多空节点和边缘情况，减少了复杂的条件判断。虚拟节点和反转链表时使用的temp节点不是一个东西。

虚拟节点处理的问题包括第一个节点在交换区间的情况。res一开始指向的是head，但在定义pre指针时，pre一开始定义在了res上。则在后面的交换过程中，改变pre的next其实有包括改变res的指向。需要注意的是，这个改变也包括在巧妙的循环控制中，当m=1时，第一个循环是不会执行的。

class Solution:
    def reverseBetween(self , head: ListNode, m: int, n: int) -> ListNode:
        res = ListNode(-1)
        res.next = head
        pre = res
        cur = head
        for i in range(1,m):
            pre = cur
            cur = cur.next
        for i in range(m,n):
            temp = cur.next
            cur.next=temp.next
            temp.next=pre.next
            pre.next=temp
        return res.next


    

自己实现的效率较低的方法，当时间充裕的情况下，这个方法问题不大。效率低是在于将链表当成了数组在操作，先拿出了几个特殊的节点，然后再操作。虽然这个方法时间复杂度仍然是O(n)，但倍数太大。同样的，空间复杂度为O(1)，但常数项较大。

class Solution:
    def reverseBetween(self , head: ListNode, m: int, n: int) -> ListNode:

        m = m - 1
        n = n - 1

        def get_k_node(head: ListNode, k: int) -> ListNode:

            if k < 0:
                return None

            if head is None:
                return None

            c = head
            for _ in range(k):
                c = c.next
            return c

        m_pre = get_k_node(head, m-1)
        m_node =  get_k_node(head, m)
        pre = m_node
        cur = get_k_node(head, m+1)
        n_node_next = get_k_node(head, n+1)
        n_node = get_k_node(head, n)

        
        for _ in range(n-m):
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
        
        m_pre = get_k_node(head, m-1)
        if m_pre is not None:
            m_pre.next = pre
        m_node.next = n_node_next

        if m == 0:
            return n_node
        else:
            return head

两种解法