反转链表 II 图解题解

这道题到底在问什么

输入

list=1→2→3→4→5→6→7→8, left=2, right=9

输出

1→9→8→7→6→5→4→3→2→10

最优解：一步一步想明白

1. 3记住三个角色：prev（锚点·不动）、cur（区间头·会沉底）、nxt（每轮被头插的那个）。
2. 4prev 从头节点 1 起步，要走到第 1 个节点（区间 [2,9] 的前一个）当锚点。
3. 5prev 停在 1（区间前驱，整段头插期间它纹丝不动）。cur 指区间第一个 2——它最终会沉到区间末尾。准备头插。
4. 6第 1 轮：cur=2 后面的 3 就是这轮要头插的 nxt。先记住它，准备从链上摘下来插到 prev=1 之后。
5. 7把 3 从当前位置摘下来（它左边那根箭头先断成 ·）。因为已经用 nxt 记住了它，断了也不丢。
6. 83 头插到 prev=1 正后方（箭头掉成 ←，变绿表示已就位）。它现在是区间已翻部分的新头。 cur 仍是 2，继续摘下一个。
7. 9第 2 轮：cur=2 后面的 4 就是这轮要头插的 nxt。先记住它，准备从链上摘下来插到 prev=1 之后。
8. 10把 4 从当前位置摘下来（它左边那根箭头先断成 ·）。因为已经用 nxt 记住了它，断了也不丢。
9. 114 头插到 prev=1 正后方（箭头掉成 ←，变绿表示已就位）。它现在是区间已翻部分的新头。 cur 仍是 2，继续摘下一个。
10. 12第 3 轮：cur=2 后面的 5 就是这轮要头插的 nxt。先记住它，准备从链上摘下来插到 prev=1 之后。
11. 13把 5 从当前位置摘下来（它左边那根箭头先断成 ·）。因为已经用 nxt 记住了它，断了也不丢。
12. 145 头插到 prev=1 正后方（箭头掉成 ←，变绿表示已就位）。它现在是区间已翻部分的新头。 cur 仍是 2，继续摘下一个。
13. 15第 4 轮：cur=2 后面的 6 就是这轮要头插的 nxt。先记住它，准备从链上摘下来插到 prev=1 之后。
14. 16把 6 从当前位置摘下来（它左边那根箭头先断成 ·）。因为已经用 nxt 记住了它，断了也不丢。
15. 176 头插到 prev=1 正后方（箭头掉成 ←，变绿表示已就位）。它现在是区间已翻部分的新头。 cur 仍是 2，继续摘下一个。
16. 18第 5 轮：cur=2 后面的 7 就是这轮要头插的 nxt。先记住它，准备从链上摘下来插到 prev=1 之后。
17. 19把 7 从当前位置摘下来（它左边那根箭头先断成 ·）。因为已经用 nxt 记住了它，断了也不丢。
18. 207 头插到 prev=1 正后方（箭头掉成 ←，变绿表示已就位）。它现在是区间已翻部分的新头。 cur 仍是 2，继续摘下一个。
19. 21第 6 轮：cur=2 后面的 8 就是这轮要头插的 nxt。先记住它，准备从链上摘下来插到 prev=1 之后。
20. 22把 8 从当前位置摘下来（它左边那根箭头先断成 ·）。因为已经用 nxt 记住了它，断了也不丢。
21. 238 头插到 prev=1 正后方（箭头掉成 ←，变绿表示已就位）。它现在是区间已翻部分的新头。 cur 仍是 2，继续摘下一个。
22. 24第 7 轮：cur=2 后面的 9 就是这轮要头插的 nxt。先记住它，准备从链上摘下来插到 prev=1 之后。
23. 25把 9 从当前位置摘下来（它左边那根箭头先断成 ·）。因为已经用 nxt 记住了它，断了也不丢。
24. 269 头插到 prev=1 正后方（箭头掉成 ←，变绿表示已就位）。它现在是区间已翻部分的新头。 区间内最后一个也翻好了。
25. 27区间 [2,9] 整段翻好：9→8→7→6→5→4→3→2。区间外的 1 和 10 一根箭头都没动。整条变成 1→9→8→7→6→5→4→3→2→10，返回头节点 1。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

def reverseBetween(head, left, right):
    dummy = ListNode(0, head)
    prev = dummy
    for _ in range(left - 1):      # ① 走到区间前驱
        prev = prev.next
    cur = prev.next               # 区间第一个(会沉底)
    for _ in range(right - left):  # ② 头插 right-left 次
        nxt = cur.next
        cur.next = nxt.next        #   把 nxt 摘下
        nxt.next = prev.next       #   nxt 插到 prev 之后
        prev.next = nxt
    return dummy.next

ListNode* reverseBetween(ListNode* head,int left,int right){
    ListNode dummy(0); dummy.next = head;
    ListNode* prev = &dummy;
    for(int i=0;i<left-1;i++) prev = prev->next;
    ListNode* cur = prev->next;
    for(int i=0;i<right-left;i++){
        ListNode* nxt = cur->next;
        cur->next = nxt->next;
        nxt->next = prev->next;
        prev->next = nxt;
    }
    return dummy.next;
}

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(0, head);
        ListNode prev = dummy;
        for (int i = 0; i < left - 1; i++) prev = prev.next;
        ListNode cur = prev.next;
        for (int i = 0; i < right - left; i++) {
            ListNode nxt = cur.next;
            cur.next = nxt.next;
            nxt.next = prev.next;
            prev.next = nxt;
        }
        return dummy.next;
    }
}

复杂度

面试官可能追问