LeetCode 21：合併兩個有序鏈表 - 雙指針原地合併

問題描述

將兩個升序鏈表合併為一個新的升序鏈表，並返回合併後的頭節點。要求原地操作，不創建新節點。

雙指針迭代法

維護三個指針：

• l1、l2：分別指向兩個鏈表當前待處理節點
• cur：指向新鏈表尾部，用於連接較小節點

每輪比較 l1->val 和 l2->val，將較小者接到 cur->next，並推進對應指針。

完整代碼

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // 邊界處理
        if (!l1) return l2;
        if (!l2) return l1;
        
        // 確定新頭節點
        ListNode* head = nullptr;
        if (l1->val <= l2->val) {
            head = l1; l1 = l1->next;
        } else {
            head = l2; l2 = l2->next;
        }
        head->next = nullptr;  // 斷開原連接
        ListNode* cur = head;
        
        // 合併主循環
        while (l1 && l2) {
            if (l1->val <= l2->val) {
                cur->next = l1;
                l1 = l1->next;
            } else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
            cur->next = nullptr;  // 重要：斷開舊連接，防止殘留指針
        }
        
        // 接上剩餘部分
        if (l1) cur->next = l1;
        if (l2) cur->next = l2;
        
        return head;
    }
};

關鍵細節

• 頭節點初始化：單獨處理第一個節點，避免虛擬頭節點額外空間
• 斷開舊連接：cur->next = nullptr 防止原鏈表殘留指針導致環或錯誤連接
• 尾部處理：循環結束後直接接上非空鏈表剩餘部分，利用已有序性

遞歸寫法（簡潔但棧空間 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;
    }
}

複雜度對比

測試用例

l1: 1->2->4, l2: 1->3->4  ->  1->1->2->3->4->4
l1: null, l2: 0            ->  0
l1: 5, l2: 1->2->3         ->  1->2->3->5