LeetCode 合併兩個有序鏈表：遞歸與迭代雙解法

題目描述

將兩個升序鏈表合併為一個新的升序鏈表並返回。新鏈表由原兩鏈表的節點拼接而成（即不創建新節點，只調整指針）。

解題思路

遞歸法

比較兩鏈表頭節點值，較小者作為合併後的頭，其 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(1)）

使用虛擬頭節點 dummy，尾指針 tail 不斷接入較小節點，最後連接剩餘非空鏈表。

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)，m、n 為兩鏈表長度
• 空間：遞歸 O(m+n) 棧空間；迭代 O(1)

C 語言版本（原題代碼）

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    struct ListNode* head = NULL;
    if (l1->val < l2->val) { head = l1; l1 = l1->next; }
    else { head = l2; l2 = l2->next; }
    struct ListNode* p = head;
    while (l1 && l2) {
        if (l1->val < l2->val) { p->next = l1; l1 = l1->next; }
        else { p->next = l2; l2 = l2->next; }
        p = p->next;
    }
    p->next = l1 ? l1 : l2;
    return head;
}