92. Reverse Linked List II

題目 / Problem

中文：給定一個單向鏈結串列（singly linked list）的頭節點 head，以及兩個整數 left 和 right（保證 left <= right）。請把從第 left 個位置到第 right 個位置之間的節點「反轉」，然後回傳整條串列的頭節點。位置從 1 開始計數。

English: Given the head of a singly linked list and two integers left and right (with left <= right), reverse the nodes of the list from position left to position right (positions are 1-indexed), and return the head of the modified list.

Constraints / 約束 - 節點數量 n 滿足 1 <= n <= 500。 - -500 <= Node.val <= 500。 - 1 <= left <= right <= n。

Worked Example / 範例

Input:  head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

只反轉第 2 到第 4 個節點（2,3,4 → 4,3,2），其餘不動。 Only nodes at positions 2 through 4 (2,3,4) are reversed into 4,3,2; the rest stay put.

名詞解釋 / Glossary

• 鏈結串列 / Linked list：一種資料結構，由一串「節點（node）」組成，每個節點存一個值（val）和一個指向下一個節點的指標（next）。跟陣列不同，節點在記憶體裡不連續，只能從頭沿著 next 一個一個走。A chain of nodes where each node holds a value and a pointer to the next node; you can only walk forward via next.
• 指標 / Pointer：一個存「記憶體位址」的變數。在 C 裡 ListNode *p 表示 p 指向某個節點；p->next 就是「順著 p 找到那個節點的 next 欄位」。A variable that stores the address of a node; p->next accesses the next field of the node p points to.
• 虛擬頭節點 / Dummy node：一個我們自己臨時 new 出來、放在真正 head 前面的假節點。它讓「反轉區段包含原本的第一個節點」這種邊界情況也能用同一套程式碼處理，不用特判。An extra fake node placed before the real head so that edge cases (like reversing from position 1) need no special handling.
• 原地反轉 / In-place reversal：不另外開新串列，只是改動節點之間的 next 指向，就把順序反過來。空間只用常數個額外指標。Reversing by rewiring next pointers rather than allocating a new list; uses only O(1) extra space.
• 頭插法 / Head-insertion technique：反轉一段串列的常用手法。固定住區段前一個節點，然後把區段內後面的節點一個一個「拔出來、插到最前面」，自然形成反轉。Repeatedly take the node just after the reversed section and splice it to the front of that section.
• 一次遍歷 / One pass：只從頭到尾走一遍串列就完成任務，時間 O(n)。Solving the problem while traversing the list only once.

思路

中文：最直覺的暴力法是：把第 left 到 right 個節點的值抓出來放進一個陣列，反轉陣列，再寫回去。這能通過，但需要額外 O(n) 空間，而且沒有真正練到「操作指標」。我們想要更漂亮的原地做法。

核心觀察是：反轉一段串列，其實就是把這段節點之間的 next 箭頭全部掉頭。難點在於邊界——反轉區段的前一個節點要接到新的頭，反轉區段的原頭（會變成尾巴）要接到區段後面的節點。為了不去特判「left == 1（反轉包含真正 head）」這種情況，我們先造一個 dummy 虛擬節點放在 head 前面，讓每個真實節點前面都保證有一個「前驅」。

具體做法用頭插法：先走 left - 1 步，讓指標 prev 停在反轉區段的前一個節點。此時 prev->next 就是區段的第一個節點，我們叫它 curr——注意 curr 在整個過程中「原地不動」，它會慢慢沉到區段的尾端。接著重複 right - left 次：每次把 curr 後面那個節點（叫 moved）拔出來，插到 prev 的正後方（也就是區段最前面）。每插一次，就有一個節點被「翻」到前面，做 right - left 次後整段就反轉好了。這個方法只走一遍、只用幾個指標，時間 O(n)、空間 O(1)，正好回答了 follow up 的「一次遍歷」。

關鍵不變量（invariant）：每一輪之後，prev 永遠緊貼在「已反轉部分」的前面，curr 永遠是「已反轉部分」的最後一個節點（原本的區段頭）。只要維持這兩點，指標接線就不會亂。

English: The brute-force idea is to copy values at positions left..right into an array, reverse the array, and write them back. It works but costs O(n) extra space and dodges the real skill of pointer surgery. We want a clean in-place solution instead.

The key insight: reversing a segment just means flipping every next arrow inside it. The tricky part is the boundary — the node before the segment must connect to the new segment head, and the segment's original head (which becomes the tail) must connect to whatever follows the segment. To avoid special-casing left == 1 (where the reversal includes the real head), we add a dummy node in front of head, guaranteeing every real node has a predecessor.

We use the head-insertion technique: first walk left - 1 steps so a pointer prev sits on the node just before the segment. Then prev->next is the segment's first node, call it curr — importantly curr stays in place the whole time and gradually sinks to become the segment's tail. Now repeat right - left times: take the node right after curr (call it moved), unhook it, and splice it directly after prev (the front of the segment). Each splice flips one more node to the front; after right - left splices the whole segment is reversed. This makes a single pass with only a few pointers — O(n) time, O(1) space — which answers the "one pass" follow-up.

Invariant to hold: after every round, prev stays immediately before the reversed portion, and curr stays as the last node of the reversed portion (the original segment head). Keep those two facts true and the rewiring never gets tangled.

逐步走查 / Walkthrough

Input: head = [1,2,3,4,5], left = 2, right = 4. We reverse positions 2–4.

Setup: create dummy -> 1 -> 2 -> 3 -> 4 -> 5. Walk left - 1 = 1 step so prev points at node 1. Then curr = prev->next = node 2. We will loop right - left = 2 times.

注意 curr（節點 2）從頭到尾沒動，只是後面的鄰居越來越少，最後它變成反轉段的尾巴，剛好接著節點 5。 Notice curr (node 2) never moves; it just loses its followers one by one and ends up as the segment's tail, correctly linked to node 5.

Final: drop the dummy and return dummy->next = node 1, giving [1,4,3,2,5]. ✅

Solution — C

/*
 * 演算法 / Algorithm: 頭插法原地反轉 (head-insertion in-place reversal).
 * 用 dummy 節點避免 left==1 的特判；prev 停在區段前一個節點，
 * curr 固定為區段原頭，反覆把 curr 後面的節點插到 prev 之後，共 right-left 次。
 * One pass, O(1) extra space.
 */

// LeetCode 給定的節點定義 / LeetCode's node definition:
// struct ListNode { int val; struct ListNode *next; };

struct ListNode* reverseBetween(struct ListNode* head, int left, int right) {
    // 建一個虛擬頭節點，val 隨便填 0，next 先接到真正的 head。
    // Create a dummy node so the real head always has a predecessor.
    struct ListNode dummy;              // 直接放在堆疊上，不用 malloc / stack-allocated, no malloc needed
    dummy.next = head;                  // dummy 指向原本的 head / dummy points to the original head

    // prev 會停在「反轉區段前一個節點」。從 dummy 出發走 left-1 步。
    // prev will land on the node just before the segment; start at dummy.
    struct ListNode* prev = &dummy;     // &dummy 取 dummy 的位址 / take the address of dummy
    for (int i = 0; i < left - 1; i++)  // 走 left-1 步 / advance left-1 times
        prev = prev->next;              // 沿著 next 前進一格 / step forward along next

    // curr 是反轉區段的原始頭節點，整個過程它「原地不動」，最後變成尾巴。
    // curr is the segment's original head; it stays put and becomes the tail.
    struct ListNode* curr = prev->next; // prev 後面第一個節點 / first node of the segment

    // 重複 right-left 次頭插 / repeat the head-insertion right-left times.
    for (int i = 0; i < right - left; i++) {
        // moved 是要被搬走的節點，就是 curr 後面那一個。
        // moved is the node we splice to the front — the one right after curr.
        struct ListNode* moved = curr->next;   // 取出待搬節點 / grab the node to move

        // 步驟 1：把 moved 從原位置拆下——curr 直接跳過它接到 moved 的下一個。
        // Step 1: unhook moved — curr skips over it to moved->next.
        curr->next = moved->next;

        // 步驟 2：把 moved 插到 prev 正後方（也就是區段最前面）。
        // Step 2: splice moved right after prev (the front of the segment).
        moved->next = prev->next;              // moved 接到目前的區段頭 / moved points to current segment head
        prev->next = moved;                    // prev 改指向 moved / prev now points to moved
    }

    // dummy.next 就是（可能已更新的）新頭節點 / dummy.next is the new head.
    return dummy.next;
}

Solution — C++

/*
 * 演算法 / Algorithm: 頭插法原地反轉 (head-insertion in-place reversal).
 * 與 C 版完全相同的邏輯：dummy 消除邊界、prev 固定在區段前、
 * curr 固定為區段原頭，反覆把 curr 後面的節點頭插到 prev 之後。
 * One pass, O(1) extra space.
 */

// struct ListNode { int val; ListNode *next; ... }; 由 LeetCode 提供 / provided by LeetCode.

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        // dummy 虛擬頭節點，避免 left==1 時要特判真正的 head。
        // Dummy node removes the special case when the segment includes the real head.
        ListNode dummy{0, head};        // 用大括號初始化：val=0, next=head / brace-init: val=0, next=head
        ListNode* prev = &dummy;        // prev 之後會停在區段前一個節點 / prev will sit before the segment

        // 走 left-1 步，把 prev 移到反轉區段前面。
        // Walk left-1 steps to position prev before the segment.
        for (int i = 0; i < left - 1; ++i)
            prev = prev->next;          // 前進一格 / step one node forward

        // curr 固定為區段原頭，最終沉為尾巴 / curr is the fixed segment head, becomes the tail.
        ListNode* curr = prev->next;

        // 頭插 right-left 次 / perform head-insertion right-left times.
        for (int i = 0; i < right - left; ++i) {
            ListNode* moved = curr->next;   // 待搬節點 = curr 後面那個 / node to move = the one after curr
            curr->next = moved->next;       // 從鏈上拆下 moved / unhook moved from the chain
            moved->next = prev->next;        // moved 接到目前區段頭 / moved points to current segment head
            prev->next = moved;              // prev 改指向 moved，完成頭插 / prev now points to moved
        }

        // 回傳新頭 / return the (possibly new) head.
        return dummy.next;
    }
};

複雜度 / Complexity

• Time: O(n) — 我們只用一個迴圈把 prev 走到區段前（最多 left-1 步），再做 right-left 次頭插，兩者相加不超過走完整條串列一遍。n 指節點總數，主導項是這一趟遍歷。We walk to the segment (≤ left-1 steps) then splice right-left times; together bounded by one pass over the n nodes.
• Space: O(1) — 只用了 dummy、prev、curr、moved 幾個固定的指標，不隨 n 增長；反轉是原地改指標，沒有額外配置串列或陣列。Only a constant number of pointers; the reversal rewires existing nodes with no extra list or array.

Pitfalls & Edge Cases

• 忘記 dummy 導致 left == 1 崩潰 / Missing dummy breaks left == 1：若反轉區段包含真正的 head，prev 就沒有「前一個節點」可站。dummy 保證每個真實節點都有前驅，這段程式碼因此不需要特判。Without the dummy there is no predecessor for the first node; the dummy makes every case uniform.
• 誤以為要移動 curr / Wrongly moving curr：初學者常想「把 curr 往前搬」，但正確做法是 curr 不動，搬的是它後面的 moved。搞錯會讓指標打結。curr must stay fixed as the sinking tail; you move moved, not curr.
• 接線順序寫反 / Wrong rewiring order：頭插三行 curr->next = moved->next; moved->next = prev->next; prev->next = moved; 有先後依賴。若先改 prev->next 再讀 prev->next，就會弄丟節點。務必先拆 moved、再讀舊的 prev->next、最後更新 prev->next。The three assignments have data dependencies; reorder them and you lose nodes.
• 迴圈次數 off-by-one / Off-by-one in loop counts：走到區段前要 left-1 步（不是 left），頭插要做 right-left 次（不是 right-left+1）。位置是 1-indexed，容易多算一次。Positions are 1-indexed: walk left-1, splice right-left.
• left == right 不需反轉 / left == right reverses nothing：此時 right-left == 0，迴圈一次都不跑，串列原樣回傳，程式自然正確處理，無需特判。The loop runs zero times and the list is returned unchanged — handled automatically.
• 回傳值搞錯 / Returning the wrong head：一定要回傳 dummy.next 而不是原本的 head，因為當 left == 1 時頭節點已經換人了。Always return dummy.next; the head may have changed when left == 1.