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