LeetCode 92：反轉鏈表 II——區間原地反轉

題目描述

給定單鏈表頭節點 head 和兩個位置 m、n（1 ≤ m ≤ n ≤ 表長），反轉從第 m 個到第 n 個節點的區間，要求原地、單次遍歷完成。

示例

輸入：1→2→3→4→5→NULL, m=2, n=4
輸出：1→4→3→2→5→NULL

解題思路：頭插法

分兩種情況討論：

1. m == 1：反轉區間包含頭節點，需更新頭指針
2. m > 1：找到第 m-1 個節點 pre，將第 m 到 n 個節點依次摘下插到 pre 後面

核心步驟（以 m>1 為例）

1. 定位 pre（第 m-1 節點）和 cur（第 m 節點）
2. 重複 n-m 次：
   • tmp = cur->next（待移動節點）
   • cur->next = tmp->next（摘除 tmp）
   • tmp->next = pre->next（插到 pre 後）
   • pre->next = tmp

Java 實現

public ListNode reverseBetween(ListNode head, int m, int n) {
    if (head == null) return null;
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode pre = dummy;
    for (int i = 1; i < m; ++i) pre = pre.next; // 移動到第 m-1 個
    ListNode cur = pre.next;
    for (int i = 0; i < n - m; ++i) {
        ListNode tmp = cur.next;
        cur.next = tmp.next;
        tmp.next = pre.next;
        pre.next = tmp;
    }
    return dummy.next;
}

複雜度

• 時間：O(n) —— 單次遍歷
• 空間：O(1) —— 僅用常數額外指針

圖解