/*
 * 演算法 / 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;
    }
};