解題說明
Reverse Linked List II
題目描述：給定一個鏈結串列的頭節點 head，以及兩個整數 left 和 right（1 ≤ left ≤ right ≤ n）。請反轉從第 left 個節點到第 right 個節點之間的部分，並返回修改後的串列頭節點。要求只能進行一次遍歷（one-pass）。
解題思路：此題是「反轉整個鏈結串列」的進階版本，挑戰在於需要精確定位反轉區間的前後邊界，並在反轉後正確地重新連接。
核心策略：找邊界 + 局部反轉
-
建立虛擬頭節點：在
head前方放置一個 dummy 節點，使第 1 個節點也能統一處理（避免left == 1時的特殊情況）。 -
定位
pre節點：走到第left - 1個節點（即反轉區間的前一個節點），記為pre。pre是後續重新連接的關鍵錨點。 -
局部反轉：從
pre->next開始，依次將後方的節點「插入」到pre的正後方，執行right - left次。這種「頭插法（head insertion）」可以在一次遍歷中完成反轉。每次迭代：
curr是當前要移動的節點（pre->next->next）。- 將
curr從原位置摘除，插入到pre和pre->next之間。
-
無需額外重新連接：頭插法的優點是反轉過程本身就完成了邊界的連接，不需要在反轉後另外處理前後銜接。
C++ 解法
複雜度分析
時間複雜度：O(n) — 演算法分兩個階段：第一階段走到第 left - 1 個位置，最多走 O(left) 步；第二階段執行 right - left 次頭插操作。兩個階段加起來最多走訪 O(right) ≤ O(n) 個節點，整體為單次線性遍歷，符合題目的 one-pass 要求。
空間複雜度：O(1) — 只使用了固定數量的指標變數（dummy、pre、curr、nextNode），沒有額外的陣列、堆疊或遞迴呼叫堆疊，空間使用量與輸入規模無關。
虛擬碼
1. Create a dummy node; set dummy.next = head. Let pre = dummy. 2. Advance pre forward (left - 1) times so it points to the node just before position left. 3. Let curr = pre->next (the first node of the sublist to be reversed). 4. Repeat (right - left) times: a. Let nextNode = curr->next (the node to be moved to the front). b. curr->next = nextNode->next (detach nextNode from its current position). c. nextNode->next = pre->next (point nextNode to the current front of reversed sublist). d. pre->next = nextNode (insert nextNode right after pre). 5. Return dummy.next.
其他解法
收集節點後反轉值 O(n) 時間 / O(n) 空間：先走訪一遍，將第 left 到第 right 個節點的值收集到陣列中，將陣列反轉後，再走訪一遍把值填回原節點。此方法邏輯簡單，但需要 O(right - left) 的額外空間存放節點值，不如頭插法優雅。
先找邊界再標準反轉 O(n) 時間 / O(1) 空間：先定位反轉區間的起始節點和結束節點，對這段子串列執行標準的三指標反轉（prev、curr、next），然後再重新連接前後邊界。此方法需要更仔細地處理四個邊界指標（反轉前驅、反轉起點、反轉終點、反轉後繼），容易出錯，但邏輯上更接近「反轉整個串列」的擴展，有助於鞏固對串列反轉的理解。
延伸思考
- 若要進一步擴展，讓函式支援多個反轉區間（例如反轉 [1,3] 和 [5,7]），你的解法框架需要如何調整？需要注意哪些邊界條件？
- 本題的「頭插法」與直接使用三指標反轉子串列再重新連接相比，哪種方式在實作上更不容易出錯？請說明你的理由。
- 如果鏈結串列是雙向鏈結串列（每個節點有
prev和next指標），反轉操作需要額外更新哪些指標？時間和空間複雜度會改變嗎？