本文完整拆解 LeetCode 21 Merge Two Sorted Lists 的解法:從解題思路、演算法步驟到時間與空間複雜度,並整理邊界情況與 3 種解法比較,幫你把 Merge Two Sorted Lists 一次弄懂。
Explore diverse LeetCode solutions in Python, C++, JavaScript, SQL, and TypeScript. Ideal for interview prep, learning, and code practice in multiple programming languages. Github Repo Link
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Example 1:
Input: list1 = [1,2,4], list2 = [1,3,4] Output: [1,1,2,3,4,4]
Example 2:
Input: list1 = [], list2 = [] Output: []
Example 3:
Input: list1 = [], list2 = [0] Output: [0]
Constraints:
- The number of nodes in both lists is in the range
[0, 50]. -100 <= Node.val <= 100- Both
list1andlist2are sorted in non-decreasing order.
Python
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution(object):
def mergeTwoLists(self, list1, list2):
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
if list1:
current.next = list1
else:
current.next = list2
return dummy.next
Merge Two Sorted Lists 解題思路
兩條鏈結串列都已排序,所以合併時只要每次比較兩邊的頭節點,把較小的接到結果尾端即可。實作上最容易出錯的是處理「結果串列的頭」,用一個虛擬頭節點(dummy node)可以讓所有情況統一成「接在 tail 後面」,省掉大量邊界判斷。
Merge Two Sorted Lists 演算法步驟
- 建立 dummy 節點,tail 指向 dummy。
- 當兩條串列都還有節點時,比較 l1 與 l2 的值,把較小的接到 tail.next,並讓該串列往後走一步。
- 每接一個節點就把 tail 往後移動一格。
- 迴圈結束後,把還有剩餘的那一條直接接上,最後回傳 dummy.next。
Merge Two Sorted Lists 複雜度分析
| 項目 | 複雜度 |
|---|---|
| 時間複雜度 | O(m+n) |
| 空間複雜度 | O(1) |
每個節點只被處理一次,時間為兩條串列長度之和 O(m+n)。採用迭代寫法只用幾個指標變數,空間為 O(1);若改用遞迴則會有 O(m+n) 的呼叫堆疊。
Merge Two Sorted Lists 的邊界情況與常見錯誤
- 任一條串列為空時,直接回傳另一條。
- 兩邊值相同時接哪一邊都可以,但要保持穩定性就接 l1。
- 結尾一定要把剩餘串列接上,忘記會遺失節點。
- 本解法重接原有節點而非複製,呼叫端的原串列會被改動。
Merge Two Sorted Lists 其他解法比較
| 解法 | 時間 | 空間 | 說明 |
|---|---|---|---|
| 把所有節點收集後重新排序 | O((m+n)log(m+n)) | O(m+n) | 沒有利用已排序的性質 |
| 遞迴合併 | O(m+n) | O(m+n) | 程式碼優雅但有堆疊深度風險 |
| dummy 節點迭代合併 | O(m+n) | O(1) | 本文採用 |

