LeetCode 21 合併兩個有序鏈表：雙指針原地合併

問題描述

將兩個升序鏈表合併為一個新的升序鏈表並返回。新鏈表由原鏈表節點拼接而成（原地操作）。

核心算法：雙指針 + 哨兵節點

1. 創建哨兵節點 dummy，tail 指向它。
2. 雙指針 p1, p2 遍歷兩鏈表：
   • 比較 p1->val 和 p2->val，較小者接在 tail 後，對應指針前進，tail 前進。
3. 一鏈表耗盡後，將另一鏈表剩餘部分直接接在 tail 後。
4. 返回 dummy->next。

關鍵代碼 (C++)

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (l1 && l2) {
        if (l1->val <= l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    tail->next = l1 ? l1 : l2;
    return dummy.next;
}

關鍵點

• 哨兵節點：簡化頭節點特殊情況處理，代碼更簡潔。
• 原地操作：直接重組節點 next 指針，無新建節點開銷。
• 尾部拼接：剩餘部分鏈表已有序，直接整體接入。

複雜度分析

• 時間：O(m+n) — 每節點恰好訪問一次。
• 空間：O(1) — 僅使用常數額外指針。

遞歸版本（補充）

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    if (l1->val <= l2->val) {
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    }
}

遞歸版本優雅但佔用 O(m+n) 棧空間，大數據時可能棧溢出。迭代版本更穩健。

總結

LeetCode 21 是鏈表雙指針的入門經典。掌握「哨兵節點 + 尾指針 + 原地拼接」模板，可解決「合併 K 個有序鏈表、歸並排序鏈表」等進階問題。