LeetCode 86 Partition List：鏈表分區保持相對順序

題目

給定鏈表頭節點 head 和值 x，將鏈表重排使所有小於 x 的節點排在大於或等於 x 的節點之前，且保持兩部分內部原有相對順序。例如：1→4→3→2→5→2, x=3 → 1→2→2→4→3→5。

解法

使用雙指針原地調整。設置虛擬頭節點 dummy，指針 p 指向最後一個小於 x 的節點（初始指向 dummy），q 從 p->next 開始遍歷。當 q->next 存在且值 < x 時，將 q->next 移至 p 之後，並更新 p。否則 q 後移。這樣小於 x 的節點會按原序依次插入到 p 後面，大於等於 x 的節點保持原序在後。

代碼 (C++)

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        if (!head) return head;
        ListNode dummy(0);
        dummy.next = head;
        ListNode *p = &dummy, *q = p->next;
        // 移動 p 到第一個 >= x 的節點前
        while (q && q->val < x) {
            p = p->next;
            q = p->next;
        }
        while (q) {
            ListNode* tmp = q->next;
            if (!tmp) break;
            if (tmp->val < x) {
                q->next = tmp->next;      // 取出 tmp
                tmp->next = p->next;      // 插入 p 後
                p->next = tmp;
                p = p->next;              // p 後移
            } else {
                q = q->next;
            }
        }
        return dummy.next;
    }
};