LeetCode 86 Partition List：鏈表分區 (小於 x 在前)

題目描述

給定鏈表頭節點和值 x，重排鏈表使所有值 `< x` 的節點在前，`≥ x` 的在後。**保持兩部分內部相對順序不變**。

例：1→4→3→2→5→2, x=3 → 1→2→2→4→3→5

雙指針拼接法

維護兩條鏈表：`less` (小於 x) 和 `greater` (大於等於 x)。遍歷原鏈表，按值將節點**斷開**接到對應鏈表尾部。最後拼接 `less` 尾接 `greater` 頭。

代碼實現 (C++ / Java)

// C++
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode less_dummy(0), greater_dummy(0);
        ListNode *less_tail = &less_dummy, *greater_tail = &greater_dummy;
        
        while (head) {
            ListNode* next = head->next;
            head->next = nullptr; // 斷開
            if (head->val < x) {
                less_tail->next = head;
                less_tail = head;
            } else {
                greater_tail->next = head;
                greater_tail = head;
            }
            head = next;
        }
        less_tail->next = greater_dummy.next;
        return less_dummy.next;
    }
};

// Java
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode lessDummy = new ListNode(0), greaterDummy = new ListNode(0);
        ListNode lessTail = lessDummy, greaterTail = greaterDummy;
        
        while (head != null) {
            ListNode next = head.next;
            head.next = null;
            if (head.val < x) {
                lessTail.next = head;
                lessTail = head;
            } else {
                greaterTail.next = head;
                greaterTail = head;
            }
            head = next;
        }
        lessTail.next = greaterDummy.next;
        return lessDummy.next;
    }
}

完整可運行 C++ 示例

#include 
using namespace std;

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

ListNode* createList(int n) {
    ListNode *head = nullptr, *tail = nullptr;
    for (int i = 0, x; i < n && cin >> x; i++) {
        ListNode* node = new ListNode(x);
        if (!head) head = tail = node;
        else { tail->next = node; tail = node; }
    }
    return head;
}

void printList(ListNode* head) {
    while (head) { cout << head->val << " "; head = head->next; }
    cout << endl;
}

int main() {
    int n = 6, x = 3;
    ListNode* list = createList(n);
    Solution sol;
    ListNode* res = sol.partition(list, x);
    printList(res);
    return 0;
}

關鍵點

• **斷開節點 `head->next = nullptr`** 至關重要，否則拼接後可能形成環或殘留舊連接。
• 哨兵節點 (`dummy`) 簡化頭節點為空的邊界處理。
• 保持相對順序：遍歷順序即原順序，尾插法天然保序。
• 時間 O(n)，空間 O(1) (不算輸出)。