LeetCode 21 Merge Two Sorted Lists - 合併兩個有序鏈表

題目翻譯

合併兩個升序單鏈表，返回合併後的升序鏈表頭。新鏈表由原節點拼接而成（不創建新節點）。

遞歸解法（最簡潔）

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1) return l2;
        if (!l2) return l1;
        if (l1->val > l2->val) swap(l1, l2);
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    }
};

迭代解法（O(1) 空間）

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;
}

複雜度

• 時間：O(m+n)
• 空間：遞歸 O(m+n) 棧；迭代 O(1)

核心模式

虛擬頭節點 + tail 指針 是鏈表構建/合併的通用模板，可直接套用於 LeetCode 23、24、25 等題。面試時寫迭代版更穩健，遞歸版作為備選展示思維靈活性。