LeetCode 筆記：Partition List（分隔鏈表）

一、題目描述

給定鏈表頭節點 head 和值 x，重排鏈表使所有小于 x 的節點在前，大于等于 x 的節點在後。保持兩部分內部相對順序不變。

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

二、解題思路：雙鏈表拼接

創建兩個虛擬頭節點 lessHead、greaterHead，遍歷原鏈表，將節點按值分配到兩條鏈表尾部。最後將 lessTail 連接 greaterHead.next，並將 greaterTail.next 置空（防環）。

三、代碼實現（C++）

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

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode lessHead(0), greaterHead(0);
        ListNode *lessTail = &lessHead, *greaterTail = &greaterHead;
        while (head) {
            if (head->val < x) {
                lessTail->next = head;
                lessTail = head;
            } else {
                greaterTail->next = head;
                greaterTail = head;
            }
            head = head->next;
        }
        lessTail->next = greaterHead.next;
        greaterTail->next = nullptr; // 關鍵：斷開尾部防環
        return lessHead.next;
    }
};

四、複雜度分析

• 時間複雜度：O(N)
• 空間複雜度：O(1)，只用常數指針

注意必須將大於等于部分的尾節點 next 置空，否則可能形成環導致死循環。