/*
 * 演算法 / Algorithm:
 * 與 C 版相同:虛擬頭節點 + 尾指標,逐一比較接上較小節點,
 * 最後把剩餘串列整段接上。原地接合,不新建節點。
 * Same as the C version: dummy head + tail pointer, splice the smaller node
 * each step, then attach the leftover. In-place, no new nodes allocated.
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        // dummy 是堆疊上的虛擬頭節點;只用它的 next 當結果起點
        // dummy is a stack-allocated placeholder head; we only use its next as the result anchor
        ListNode dummy;

        // tail 指向結果目前的最後一個節點,初始為 dummy 的位址
        // tail points at the last node of the result; initialized to dummy's address
        ListNode* tail = &dummy;   // & 取位址 / & takes the address of dummy

        // 兩條都非空時才需要比較
        // Compare only while both lists have nodes remaining
        while (list1 && list2) {   // 指標非 nullptr 在 C++ 視為 true / a non-null pointer is truthy
            // 取值較小的節點接上;<= 讓相等時優先取 list1,維持穩定
            // Splice the node with the smaller value; <= prefers list1 on ties (stable)
            if (list1->val <= list2->val) {
                tail->next = list1;    // 接上 list1 節點 / append list1's node
                list1 = list1->next;   // list1 前進 / advance list1
            } else {
                tail->next = list2;    // 接上 list2 節點 / append list2's node
                list2 = list2->next;   // list2 前進 / advance list2
            }
            tail = tail->next;         // tail 跟到新的尾端 / move tail to the new tail
        }

        // 其中一條已走完;剩下那條本身已排序,整段接上
        // One list is exhausted; the other's remainder is already sorted — attach it directly
        tail->next = list1 ? list1 : list2;   // 三元運算子:非空取 list1,否則 list2 / ternary picks the non-null one

        // 回傳真正的頭節點 / return the real head
        return dummy.next;             // dummy 是值型別,用 . 存取成員 / dummy is a value, use . to access members
    }
};