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

題目描述

合併兩個升序鏈表為一個新升序鏈表，要求通過拼接原節點實現（不創建新節點）。

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

• 設置 dummy 頭節點，tail 指向結果鏈表尾部。
• 比較 l1、l2 當前節點值，較小者接在 tail 後，推進對應指針與 tail。
• 一條鏈表遍歷完後，直接連接另一條剩餘部分。
• 返回 dummy->next。

參考代碼 (C++)

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummy(0), *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(1)，僅使用常數額外指針。

遞歸寫法（簡潔但棧深度 O(m+n)）

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