LeetCode Merge Two Sorted Lists：遞歸與迭代雙解法合併有序鏈表

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

標準歸並邏輯：比較兩鏈表頭節點，取小者接入結果表，對應指針後移。虛擬頭節點簡化邊界處理。

迭代法（推薦）

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

遞歸法

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)，空間：迭代 O(1)，遞歸 O(m+n) 棧空間。
• 面試首選迭代，代碼簡潔且無棧溢出風險。