LeetCode 21 Merge Two Sorted Lists：有序鏈表合併經典解法

LeetCode 21 基礎題目：合併兩個已排序的單向鏈表，返回新的有序鏈表。核心考察指針操作、邊界條件處理與虛擬頭節點技巧。

解法：雙指針歸併 + 虛擬頭節點

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // 邊界條件：任一為空直接返回另一個
        if (!l1) return l2;
        if (!l2) return l1;
        
        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;
    }
};

核心技巧解析

1. 虛擬頭節點

無 dummy: 需特殊處理 head 選擇、head 移動
有 dummy: 統一用 tail->next 插入，最後返回 dummy.next

2. 邊界條件優先處理

• 提前返回 l1 或 l2 為空的情況
• 避免主迴圈內額外判斷，減少分支預測失敗
• 剩餘節點直接接上，利用鏈表已有序特性

3. 就地合併

不創建新節點，直接重組現有節點的 next 指針，空間複雜度 O(1)。

複雜度分析

測試用例覆蓋

常見錯誤避坑

• 忘記處理空鏈表輸入 → 空指針解引用
• 漏掉 tail = tail->next → 死循環或丟失節點
• 剩餘節點處理邏輯錯誤 → 截斷鏈表
• 未使用虛擬頭節點 → 頭部插入邏輯冗長易錯

遞歸版本 (參考)

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) 遞歸棧，不推薦大數據量使用