題目說明

21. Merge Two Sorted Lists
    給定兩個已經按照遞增排序的連結串列，請將它們合併為一個新的排序後連結串列，並回傳新的頭節點。

範例

Input:
list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Python 解法

解法 1：遞迴

class ListNode:
def init(self, val=0, next=None):
self.val = val
self.next = next

def mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode:
if not list1 or not list2:
return list1 or list2
if list1.val < list2.val:
list1.next = mergeTwoLists(list1.next, list2)
return list1
else:
list2.next = mergeTwoLists(list1, list2.next)
return list2

解法 2：迭代（使用 Dummy 節點）

def mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode:
dummy = ListNode()
current = dummy
while list1 and list2:
if list1.val < list2.val:
current.next = list1
list1 = list1.next
else:
current.next = list2
list2 = list2.next
current = current.next
current.next = list1 or list2
return dummy.next

Java 解法

解法 1：遞迴

class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if (list1 == null) return list2;
if (list2 == null) return list1;
if (list1.val < list2.val) {
list1.next = mergeTwoLists(list1.next, list2);
return list1;
} else {
list2.next = mergeTwoLists(list1, list2.next);
return list2;
}
}
}

解法 2：迭代

class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode(0);
ListNode current = dummy;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
current.next = list1;
list1 = list1.next;
} else {
current.next = list2;
list2 = list2.next;
}
current = current.next;
}
current.next = (list1 != null) ? list1 : list2;
return dummy.next;
}
}

⏱️ 複雜度分析

• 時間複雜度： O(n + m)，需遍歷兩個串列中所有節點。

• 空間複雜度：

  • 遞迴：O(n + m)（遞迴堆疊）
  • 迭代：O(1)（僅使用指標）