/*
 * 演算法 / Algorithm:
 * 用虛擬頭節點 dummy + 尾指標 tail,每次比較兩條串列最前面的節點,
 * 把較小的接到結果尾端,直到某條走完,再把另一條剩餘部分整段接上。
 * Use a dummy head + tail pointer; repeatedly splice the smaller front
 * node onto the result, then attach the leftover of whichever list remains.
 */

// LeetCode 的節點定義 (通常題目已給,這裡為了自足而寫出)
// LeetCode's node definition (usually provided; shown here for completeness)
struct ListNode {
    int val;                  // 節點存的整數值 / the integer value in this node
    struct ListNode *next;    // 指向下一個節點的指標 / pointer to the next node
};

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    // 虛擬頭節點:放在堆疊上,val 不重要,只借用它的 next 當結果的起點
    // Dummy head on the stack; its val is irrelevant, we only use its next as the result's anchor
    struct ListNode dummy;

    // tail 一直指向「結果串列目前最後一個節點」,初始就是 dummy 本身
    // tail always points at the current last node of the result; starts at dummy
    struct ListNode *tail = &dummy;   // &dummy 取 dummy 的位址 / &dummy takes dummy's address

    // 只要兩條串列都還有節點,就繼續比較
    // While BOTH lists still have nodes, keep comparing
    while (list1 != NULL && list2 != NULL) {
        // 比較兩個最前端節點的值,取較小的接上 (<= 保證相等時的相對順序穩定)
        // Compare the two front values; take the smaller (<= keeps stable order on ties)
        if (list1->val <= list2->val) {
            tail->next = list1;       // 把 list1 的節點接到結果尾端 / splice list1's node onto the result
            list1 = list1->next;      // list1 前進一格 / advance list1
        } else {
            tail->next = list2;       // 否則接 list2 的節點 / otherwise splice list2's node
            list2 = list2->next;      // list2 前進一格 / advance list2
        }
        tail = tail->next;            // tail 移到剛接上的新尾節點 / move tail to the newly appended node
    }

    // 迴圈結束時,至少有一條已為 NULL。把另一條「剩下的整段」直接接上即可
    // On exit, at least one list is NULL; attach the remaining tail of the other in one shot
    // (若兩條都空,list1 為 NULL,接上 NULL 也正確 / if both empty, attaching NULL is still correct)
    tail->next = (list1 != NULL) ? list1 : list2;

    // 真正的頭是 dummy->next;dummy 只是佔位,丟棄不管
    // The real head is dummy->next; the dummy itself is discarded
    return dummy.next;                // 用 . 因為 dummy 是實體變數不是指標 / use . since dummy is a value, not a pointer
}