21. Merge Two Sorted Lists

題目 / Problem

中文： 給你兩條「已排序」的鏈結串列的頭節點 list1 和 list2。請把這兩條串列合併成「一條」仍然保持升序排列的串列。合併的方式是把原本兩條串列裡的節點「接」起來（不需要新建節點，直接串接原有節點即可）。最後回傳合併後串列的頭節點。

English: You are given the heads of two sorted linked lists list1 and list2. Merge them into a single sorted list by splicing together the existing nodes (you don't need to create new nodes — just re-link the ones you already have). Return the head of the merged list.

約束 / Constraints: - 兩條串列的節點總數在 [0, 50] 範圍內 / The number of nodes in both lists is in the range [0, 50]. - -100 <= Node.val <= 100 - 兩條串列都按「非遞減」順序排好 / Both lists are sorted in non-decreasing order.

範例 / Worked Example:

Input:  list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

名詞解釋 / Glossary

• 鏈結串列 / Linked list：一種資料結構，由一連串「節點（node）」組成，每個節點存一個值 val，以及一個指向下一個節點的指標 next。最後一個節點的 next 指向空（NULL / nullptr）。A chain of nodes where each node holds a value and a pointer to the next node; the last node points to null.

• 頭節點 / Head：串列的第一個節點。只要抓住頭節點，就能沿著 next 走完整條串列。The first node of a list; from it you can walk the whole list via next.

• 指標 / Pointer：一個「存位址」的變數。node->next 表示「跟著這個節點的 next 位址去找下一個節點」。A variable that stores an address; node->next follows the link to the next node.

• 虛擬頭節點 / Dummy node：一個我們臨時造出來、不屬於答案的假節點，放在結果串列的最前面。有了它，第一個真正節點的接法就跟後面所有節點一模一樣，省去「這是不是第一個」的特判。A fake placeholder node placed before the real result so that inserting the first node uses the same code as every other node, avoiding special-casing the head.

• 尾指標 / Tail pointer：一個一直指向「目前結果串列最後一個節點」的指標，方便我們把新節點接在後面。A pointer that always points at the last node of the result so we can append in O(1).

• 原地接合 / Splicing (in-place)：不 malloc/new 新節點，只改動原節點的 next 指向，把它們重新串成一條。Reusing the original nodes and only rewiring their next links instead of allocating new nodes.

思路

最直覺的暴力想法是：把兩條串列的所有值倒進一個陣列，排序後再重新建一條串列。這樣雖然正確，但完全浪費了「兩條串列本來就已經排好序」這個關鍵條件，還要額外開陣列、重新建節點，時間是 O((m+n) log(m+n))，空間也多。既然兩邊都已排序，我們其實可以像「合併撲克牌」一樣：兩手各拿一疊排好的牌，每次比較兩疊最上面那張，把比較小的那張抽出來放到結果堆的最後面，一直重複到某一疊空了為止。這就是合併排序（merge sort）裡的「合併」步驟。為了讓「接第一個節點」跟「接後面的節點」邏輯統一，我們造一個虛擬頭節點 dummy，再用一個尾指標 tail 一直指向結果的最後一個節點。每一步：比較 list1->val 和 list2->val，把較小的那個節點接到 tail->next，然後 tail 往前移一格，被選中的那條串列也往後走一格。核心不變量（invariant）是：dummy 到 tail 這一段永遠是已合併好、且排序正確的結果。當其中一條走完，另一條「剩下的部分」本身就是排好序的，直接一次接到 tail->next 即可。最後回傳 dummy->next（真正的頭），dummy 本身丟掉。

The brute-force idea is to dump every value into an array, sort it, and rebuild a list — correct, but it throws away the fact that both inputs are already sorted, costing O((m+n) log(m+n)) time plus extra space. Since both lists are sorted, we can instead merge them like two sorted piles of cards: repeatedly compare the front card of each pile, pull out the smaller one, and place it at the end of the result pile, until one pile is empty. This is exactly the "merge" step of merge sort. To make appending the first node behave identically to appending every later node, we create a dummy head node and keep a tail pointer at the end of the result. Each step: compare list1->val and list2->val, splice the smaller node onto tail->next, advance tail, and advance whichever list we took from. The invariant is that the segment from dummy to tail is always a correctly-sorted merged prefix. Once one list runs out, the remainder of the other is already sorted, so we attach it in one shot. Finally we return dummy->next (the real head) and discard the dummy.

逐步走查 / Walkthrough

Input: list1 = [1,2,4], list2 = [1,3,4]

We start with a dummy node; tail points at dummy. Result so far (after dummy) is empty.

At step 6 list1 is NULL, so we attach the entire remainder of list2 (4) at once. Final answer = dummy->next = [1,1,2,3,4,4]. ✅

Solution — C

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

Solution — C++

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

複雜度 / Complexity

• Time: O(m + n) — m 和 n 分別是兩條串列的長度。每個節點只被「比較並接上」一次,迴圈總步數不超過 m+n,剩餘部分是 O(1) 的整段接合。Each node is visited and spliced exactly once; the loop runs at most m+n times and attaching the leftover is O(1). Here m, n are the two list lengths.
• Space: O(1) — 只用了 dummy、tail、list1、list2 幾個固定指標,沒有隨輸入增長的額外空間,節點都是原地重接。Only a constant number of pointers; no allocation, nodes are re-linked in place. (Note: a recursive merge would use O(m+n) stack space — this iterative version avoids that.)

Pitfalls & Edge Cases

• 空串列 / Empty list(s): 若某條一開始就是 NULL,while 條件立刻為假,直接把另一條(可能也是 NULL)接上並回傳,結果正確。The dummy + final attach handles []+[]→[] and []+[0]→[0] with no special code.
• 忘了移動 tail / Forgetting to advance tail: 若接上節點後沒有 tail = tail->next,下一次接合會覆蓋掉剛接的節點,結果只剩一個節點。The tail = tail->next line is essential — without it each append overwrites the previous one.
• 回傳 dummy 而非 dummy.next / Returning the dummy itself: 別忘了答案的頭是 dummy.next;回傳 &dummy 會多帶一個垃圾節點。Return dummy.next, not the dummy — otherwise you prepend a junk node.
• 相等時的比較 <= vs <: 兩者都會通過測試,但用 <= 在相等時優先取 list1,讓合併是「穩定的」;這在合併排序的正確性上是好習慣。Using <= keeps the merge stable on equal values — a good habit even though < also passes here.
• 不要新建節點 / Don't allocate new nodes: 題目要求「splice」既有節點。用 malloc/new 複製值雖然也能過,但浪費記憶體,且不符合原地接合的意圖。The problem asks you to splice existing nodes; copying into freshly allocated nodes wastes memory and misses the point.
• 懸空的最後一個 next / Dangling final next: 因為結尾一定接上某條串列的剩餘(其最後節點的 next 本就是 NULL),結果串列自然正確終止,不需手動設 NULL。The final list terminates correctly because the attached remainder already ends in NULL.