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

題目大意

給定單鏈表頭節點 head 和值 x，重排鏈表使所有值 < x 的節點在前，值 ≥ x 的節點在後，且保持兩部分內部原有相對順序。返回新頭節點。

雙指鏈表法

創建兩個虛擬頭節點 h1, h2，尾指針 p1, p2。遍歷原鏈表：

• 值 < x：接到 p1 後，p1 後移。
• 值 ≥ x：接到 p2 後，p2 後移。

遍歷結束後，p1->next = h2.next，p2->next = nullptr（防環），返回 h1.next。

代碼實現

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode h1(0), h2(0);
        ListNode *p1 = &h1, *p2 = &h2;
        while (head) {
            if (head->val < x) {
                p1->next = head;
                p1 = p1->next;
            } else {
                p2->next = head;
                p2 = p2->next;
            }
            head = head->next;
        }
        p2->next = nullptr; // 關鍵：斷開原鏈表可能的環
        p1->next = h2.next;
        return h1.next;
    }
};

常見錯誤

• 忘記 p2->next = nullptr，導致新鏈表尾部指向原鏈表中間節點形成環，運行超時。

簡潔寫法（連續賦值）

ListNode* partition(ListNode* head, int x) {
    ListNode n1(0), n2(0);
    ListNode *p1 = &n1, *p2 = &n2;
    while (head) {
        if (head->val < x) p1 = p1->next = head;
        else p2 = p2->next = head;
        head = head->next;
    }
    p2->next = nullptr;
    p1->next = n2.next;
    return n1.next;
}

複雜度

• 時間 O(n)，一次遍歷。
• 空間 O(1)，只用常數額外指針。

總結

鏈表分區雙指針法是標準解法：構建兩條鏈表收集兩類節點，最後拼接。關鍵細節是斷開第二部分鏈表尾部的 next 指針防止成環。代碼簡潔，是鏈表操作基本功考察點。