LeetCode Partition List 解題報告：鏈表分區與原地重排技巧

題目大意

給定鏈表頭節點 head 和值 x，將鏈表重排使所有 <x 的節點在前，≥x 的節點在後，保持兩部分內部相對順序。要求原地操作，O(1) 額外空間。

雙指針分區法

1. 創建兩個虛擬頭節點 dummySmall、dummyLarge，尾指針 tailS、tailL。
2. 遍歷原鏈表，將節點斷開並拼接到對應分區尾部。
3. 合併：tailS->next = dummyLarge->next; tailL->next = nullptr;
4. 返回 dummySmall->next。

完整代碼 (C++)

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode dummyS(0), dummyL(0);
        ListNode *tailS = &dummyS, *tailL = &dummyL;
        while (head) {
            ListNode *nxt = head->next;
            head->next = nullptr;
            if (head->val < x) {
                tailS->next = head;
                tailS = head;
            } else {
                tailL->next = head;
                tailL = head;
            }
            head = nxt;
        }
        tailS->next = dummyL.next;
        return dummyS.next;
    }
};

關鍵點解析

• 斷開 next：head->next = nullptr 防止殘留指針形成環。
• 虛擬頭節點：統一處理空分區、頭節點插入邊界。
• 保持穩定性：遍歷順序即原順序，尾插法天然穩定。

複雜度

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

變體延伸

• 三向分區（< x, = x, > x）：三個虛擬頭節點。
• 數組版 Partition（快排核心）：雙指針交換，不穩定，O(1) 空間。
• 鏈表快排：隨機選主元，分區遞歸，期望 O(n log n)。

總結

Partition List 是鏈表基本操作的綜合考察：遍歷、斷鏈、尾插、合併。虛擬頭節點+雙尾指針模板極其通用，建議熟練掌握並封裝為工具函數。