題?描述

輸?兩個單調遞增的鏈表，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表滿?單調不減規則。

如輸?{1,3,5} , {2,4,6} 時，合并后的鏈表為{1,2,3,4,5,6} ，所以對應的輸出為{1,2,3,4,5,6} ，轉換過程如下圖所示：

思路及解答

迭代法（雙指針）

使用兩個指針分別遍歷兩個鏈表，比較當前節點的值，將較小的節點連接到結果鏈表上。當一個鏈表遍歷完后，將另一個鏈表的剩余部分直接連接到最后。

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    // 創建啞節點作為合并后鏈表的頭節點前驅
    ListNode dummy = new ListNode(-1);
    ListNode current = dummy;
    
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }
    
    // 連接剩余部分
    current.next = (l1 != null) ? l1 : l2;
    
    return dummy.next;
}

• 時間復雜度?：O(n+m)，n和m分別是兩個鏈表的長度
• ?空間復雜度?：O(1)，只使用了固定數量的指針

遞歸比較

利用遞歸將問題分解：每次比較兩個鏈表的頭節點，選擇較小的節點作為合并后鏈表的頭節點，然后遞歸地合并剩余部分。

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) 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(n+m)，遞歸調用棧的深度