分析

• 本题的考点：链表。

• 因为头结点可能改变，因此需要使用虚拟头结点。

• 用m代替这里的left，用n代表这里的right。分为如下几个步骤：

（1）找到第m-1个节点a；

（2）然后将a后面n-m条边翻转；

（3）第m个节点指向第n+1个节点，让a指向第n个节点。

• 如下图：

代码

• C++

class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {

        auto dummy = new ListNode(-1);
        dummy->next = head;

        auto a = dummy;
        for (int i = 0; i < m - 1; i++) a = a->next;
        auto b = a->next, c = b->next;
        for (int i = 0; i < n - m; i++) {
            auto t = c->next;
            c->next = b;
            b = c, c = t;
        }
        a->next->next = c;
        a->next = b;
        return dummy->next;
    }
};

• Java

class Solution {

    public ListNode reverseBetween(ListNode head, int m, int n) {

        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode a = dummy;
        for (int i = 0; i < m - 1; i++) a = a.next;
        ListNode b = a.next, c = b.next;
        for (int i = 0; i < n - m; i++) {
            ListNode t = c.next;
            c.next = b;
            b = c; c = t;
        }
        a.next.next = c;
        a.next = b;

        return dummy.next;
    }
}

时空复杂度分析

• 时间复杂度：$O(n)$，n为链表长度。

• 空间复杂度：$O(1)$。