題目描述:給定一個鏈結串列的頭節點 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 之間。無需額外重新連接:頭插法的優點是反轉過程本身就完成了邊界的連接,不需要在反轉後另外處理前後銜接。
時間複雜度: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),然後再重新連接前後邊界。此方法需要更仔細地處理四個邊界指標(反轉前驅、反轉起點、反轉終點、反轉後繼),容易出錯,但邏輯上更接近「反轉整個串列」的擴展,有助於鞏固對串列反轉的理解。
prev 和 next 指標),反轉操作需要額外更新哪些指標?時間和空間複雜度會改變嗎?