86. Partition List

題目 / Problem

中文： 給定一個鏈結串列的頭節點 head 和一個整數 x，重新排列串列，使得所有小於 x 的節點都排在所有大於或等於 x 的節點之前。你必須保留每個分區中節點原本的相對順序。

English: Given the head of a linked list and a value x, partition it so that all nodes with value less than x come before all nodes with value greater than or equal to x. You must preserve the original relative order of the nodes within each of the two partitions.

Constraints / 限制： - 節點數量在 [0, 200] 範圍內 / Number of nodes is in [0, 200]. - -100 <= Node.val <= 100 - -200 <= x <= 200

Example / 範例：

Input:  head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]

小於 3 的節點是 1, 2, 2（按原順序），大於等於 3 的節點是 4, 3, 5（按原順序），接起來就是 [1,2,2,4,3,5]。 The nodes < 3 are 1, 2, 2 (in original order); the nodes >= 3 are 4, 3, 5 (in original order); concatenated they give [1,2,2,4,3,5].

名詞解釋 / Glossary

• linked list / 鏈結串列：一種資料結構，由一連串「節點」組成，每個節點存一個值 val 和一個指向下一個節點的指標 next。和陣列不同，節點在記憶體中不必連續，只能從頭沿著 next 一個一個往後走。 / A chain of "nodes"; each node stores a value val and a pointer next to the following node. Unlike an array, you can only traverse it forward one node at a time.
• node / 節點：串列中的一個元素，這裡型別是 struct ListNode { int val; struct ListNode *next; }。 / A single element of the list.
• pointer / 指標：一個變數，裡面存的是另一個變數（節點）的記憶體位址。p->next 表示「跟著 p 指的節點裡的 next 走」。 / A variable holding the memory address of another variable (node). p->next means "follow the next field of the node p points to."
• dummy node / 虛擬頭節點：一個我們自己造出來、不屬於答案的假節點，放在串列最前面。有了它，就不必為「第一個節點」寫特殊處理，程式更簡潔。 / A fake head node we create that is not part of the real data. It removes special-case handling for the first real node, simplifying the code.
• relative order / 相對順序：兩個節點誰在前誰在後的先後關係。「保留相對順序」代表若 A 原本在 B 前面，且兩者同屬一個分區，結果中 A 仍在 B 前面。 / The front-to-back ordering between nodes. "Preserving" it means if A came before B originally and both land in the same partition, A still comes before B.
• in-place / 原地：不另外複製節點，只是改動 next 指標把原有節點重新串起來。 / We don't copy nodes; we only rewire the existing nodes' next pointers.

思路

最直覺的暴力想法可能是：掃描整個串列，把小於 x 的值收集到一個陣列，把大於等於 x 的值收集到另一個陣列，再重建串列。這能做，但要額外開陣列、還要新建節點，比較笨重。其實我們不必動到節點裡的值，只要改「箭頭」（next 指標）指向誰就好。關鍵觀察是：答案就是「所有小於 x 的節點按原順序」接上「所有大於等於 x 的節點按原順序」。既然要維持兩組各自的原順序，我們只要從頭到尾走一遍，每遇到一個節點就判斷它該去哪一組，然後把它接到那一組的尾端即可。為了實作方便，我們建立兩條臨時串列：一條叫 less（放小於 x 的），一條叫 greater（放大於等於 x 的）。每條各配一個 dummy 虛擬頭節點，這樣一開始尾指標就有明確起點，不用特判空串列。走訪時用 lessTail 和 greaterTail 兩個尾指標分別記住兩條串列目前的最後一個節點，來一個接一個，天然保留了原順序。走完後把 less 的尾巴接到 greater 的頭（greaterDummy.next），並且一定要把 greaterTail.next 設成 NULL，切斷原本可能還連著的舊指標，否則會形成環。最後回傳 lessDummy.next 就是新的頭。整趟只走一遍、只用固定幾個指標，時間 O(n)、額外空間 O(1)。

The brute-force idea would be to walk the list, push values < x into one array and values >= x into another, then rebuild a list. That works but wastes memory and creates new nodes. We don't actually need to touch any node's value — we only need to rewire the next pointers. The key observation: the answer is simply "every node < x in original order" followed by "every node >= x in original order." Since each group must keep its own original order, we can make a single pass: for each node decide which group it belongs to, and append it to the tail of that group. Concretely we build two temporary lists, less and greater, each starting with a dummy head so the tail pointer always has a valid starting point and we avoid empty-list special cases. Two tail pointers, lessTail and greaterTail, remember the last node of each list, so appending is O(1) and the original order is preserved automatically. After the pass, we join the two lists: point lessTail.next to greaterDummy.next, and — critically — set greaterTail.next to NULL so no stale pointer creates a cycle. Return lessDummy.next as the new head. One pass, a handful of pointers: O(n) time, O(1) extra space.

逐步走查 / Walkthrough

Input: head = [1,4,3,2,5,2], x = 3

初始：lessDummy -> NULL，greaterDummy -> NULL，lessTail = lessDummy，greaterTail = greaterDummy。 Initially both dummy lists are empty; each tail points at its own dummy.

收尾 Finish： - greaterTail.next = NULL → 切斷 greater 尾巴 / terminate the greater list (4,3,5 ends cleanly). - lessTail.next = greaterDummy.next → 把 less 尾接到 greater 頭 / link less's tail to greater's head. - 回傳 return lessDummy.next → [1,2,2,4,3,5] ✅

Solution — C

/*
 * 演算法 / Algorithm:
 * 一次走訪，把節點分流到兩條串列：less(值 < x) 與 greater(值 >= x)，
 * 各自用 dummy 頭 + tail 指標維持原順序，最後把 less 尾接 greater 頭。
 * One pass: route nodes into two lists (less: < x, greater: >= x), each with a
 * dummy head and a tail pointer, then splice less onto greater.
 */

// LeetCode 已定義此結構 / LeetCode already defines this struct:
// struct ListNode { int val; struct ListNode *next; };

struct ListNode* partition(struct ListNode* head, int x) {
    // 建立兩個「虛擬頭節點」放在堆疊上；.next 先設為 NULL 表示空串列
    // Two dummy heads on the stack; .next = NULL means "list is empty for now"
    struct ListNode lessDummy = {0, NULL};      // less 串列的假頭 / dummy head of the "less" list
    struct ListNode greaterDummy = {0, NULL};   // greater 串列的假頭 / dummy head of the "greater" list

    // 尾指標一開始都指向自己那條串列的 dummy，代表「目前最後一個節點」
    // Tail pointers start at each dummy = "current last node of this list"
    struct ListNode *lessTail = &lessDummy;         // &x 取位址 / &x takes the address of x
    struct ListNode *greaterTail = &greaterDummy;

    // cur 從真正的頭開始，沿 next 一路往後走，直到 NULL(走到底)
    // cur walks from the real head, following next until NULL (end of list)
    struct ListNode *cur = head;
    while (cur != NULL) {
        if (cur->val < x) {                 // cur->val 是「cur 指的節點的 val」/ value of the node cur points to
            lessTail->next = cur;           // 把 cur 接到 less 尾端 / append cur to the less list
            lessTail = cur;                 // 尾指標前移到剛接上的節點 / advance the tail to the new last node
        } else {                            // 值 >= x 的情況 / value is >= x
            greaterTail->next = cur;        // 接到 greater 尾端 / append cur to the greater list
            greaterTail = cur;              // 尾指標前移 / advance the greater tail
        }
        cur = cur->next;                    // 移到下一個節點 / move on to the next node
    }

    // 重要：切斷 greater 尾巴的舊 next，避免殘留指標形成環
    // Important: terminate the greater list to avoid a stale pointer causing a cycle
    greaterTail->next = NULL;

    // 把 less 的尾巴接到 greater 的第一個真正節點 / link less's tail to greater's first real node
    lessTail->next = greaterDummy.next;

    // less dummy 的 next 就是重排後的真正頭節點 / less dummy's next is the new real head
    return lessDummy.next;
}

Solution — C++

/*
 * 演算法 / Algorithm:
 * 一次走訪，用兩個 dummy 頭 + tail 指標把節點分流成 less(<x) 與 greater(>=x)，
 * 保留原順序，最後把兩條串列接起來。只改指標，不複製節點。
 * Single pass with two dummy heads + tail pointers to split nodes into less(<x)
 * and greater(>=x), preserve order, then splice. Rewire pointers, don't copy nodes.
 */

// LeetCode 已定義 / LeetCode already defines:
// struct ListNode { int val; ListNode *next; ListNode(int v): val(v), next(nullptr) {} };

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        // 兩個 dummy 頭節點；new 在堆積上配置，值隨意(這裡用 0) / two dummy heads
        // 用智慧指標會更安全，但此處節點需存活並回傳，故直接用裸指標
        ListNode lessDummy(0);      // less 串列的假頭 / dummy head for the "less" list
        ListNode greaterDummy(0);   // greater 串列的假頭 / dummy head for the "greater" list

        // 尾指標指向各自 dummy；auto 讓編譯器自動推導型別為 ListNode*
        // Tail pointers at each dummy; `auto` lets the compiler deduce ListNode*
        ListNode* lessTail = &lessDummy;
        ListNode* greaterTail = &greaterDummy;

        // 逐一走訪原串列 / walk the original list node by node
        for (ListNode* cur = head; cur != nullptr; cur = cur->next) {
            if (cur->val < x) {             // 目前節點值小於 x / current node value < x
                lessTail->next = cur;       // 接到 less 尾端 / append to less list
                lessTail = cur;             // 尾指標前移 / advance the tail
            } else {                        // 值 >= x / value >= x
                greaterTail->next = cur;    // 接到 greater 尾端 / append to greater list
                greaterTail = cur;          // 尾指標前移 / advance the tail
            }
        }

        // 切斷 greater 尾巴，避免形成環 / terminate greater list to avoid a cycle
        greaterTail->next = nullptr;

        // 把 less 尾接上 greater 的第一個真正節點 / splice less onto greater
        lessTail->next = greaterDummy.next;

        // 回傳重排後的頭節點 / return the new head
        return lessDummy.next;
    }
};

複雜度 / Complexity

• Time: O(n) — 我們只用一個 while/for 迴圈把每個節點恰好處理一次，n 是串列的節點數；接串列與切尾都是 O(1) 的常數操作。 / We touch each of the n nodes exactly once in a single loop; splicing and terminating are O(1). n = number of nodes.
• Space: O(1) — 只用了兩個 dummy 節點和幾個指標，數量固定，不隨 n 成長；我們重用原有節點而非另外複製。 / Only two dummy nodes and a fixed handful of pointers, independent of n; we reuse existing nodes instead of copying.

Pitfalls & Edge Cases

• 忘記把 greaterTail->next 設為 NULL / Forgetting to null-terminate the greater list：greater 的最後一個節點原本的 next 可能還指著某個較前面的節點，若不切斷，串列會形成環，LeetCode 會判超時或錯誤。程式最後一步明確 greaterTail->next = NULL 就是防這件事。 / The last greater node may still point back into the list; without cutting it you create a cycle. The explicit = NULL prevents this.
• 空串列 / Empty list (head == NULL)：迴圈一次都不跑，兩條串列都空，lessDummy.next 仍是 NULL，直接回傳 NULL，正確。 / The loop never runs and we return NULL — handled naturally.
• 所有節點都在同一側 / All nodes on one side：若全部 < x，greater 為空、greaterDummy.next 是 NULL，接上去等於什麼都不接；若全部 >= x，less 為空、回傳的頭正好是 greater 的頭。dummy 節點讓這兩種情況都不需特判。 / Dummy heads make "all less" and "all greater" work without special cases.
• 邊界值相等 val == x / Boundary equality：題目是「小於」對「大於或等於」，所以 val == x 必須進 greater 組。程式用 cur->val < x 判斷，剛好把等於的情況歸到 else(greater)，符合定義。 / Since the rule is < vs >=, a node equal to x must go to greater; the < x test puts it in the else branch correctly.
• 誤以為要改節點的值 / Thinking you must change node values：不需要，也不該。我們只重接 next 指標；改值反而更難維持相對順序。 / You only rewire next; mutating values is unnecessary and error-prone.