LeetCode 21 Merge Two Sorted Lists：遞歸/迭代合併有序鏈表

題目大意

合併兩個升序鏈表為一個升序鏈表，返回新頭節點。要求拼接原節點，不創建新節點。

迭代法（推薦）

• 虛擬頭節點 `dummy`，尾指針 `tail` 指向 `dummy`。
• 雙指針 `l1`, `l2` 遍歷兩表：
  - 比較 `l1->val` 和 `l2->val`，較小者接在 `tail` 後，對應指針後移，`tail` 後移。
  - 其中一表耗盡後，將另一表剩餘部分直接接在 `tail` 後。
• 返回 `dummy->next`。

代碼

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    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(n+m)）

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(n+m)。
• 空間：迭代 O(1)，遞歸 O(n+m) 棧。

總結

Merge Two Sorted Lists 是鏈表基本操作的核心模板。**迭代 + 虛擬頭節點** 是最穩健、空間最優、工業級首選寫法。遞歸法代碼極短，適合快速寫題但需注意棧溢出風險。