Merge Two Sorted Lists 解題教學:3 種解法完整比較|LeetCode 21 Best Practice

Merge Two Sorted Lists 解題教學示意圖|LeetCode 21

本文完整拆解 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 list1 and list2 are 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 演算法步驟

  1. 建立 dummy 節點,tail 指向 dummy。
  2. 當兩條串列都還有節點時,比較 l1 與 l2 的值,把較小的接到 tail.next,並讓該串列往後走一步。
  3. 每接一個節點就把 tail 往後移動一格。
  4. 迴圈結束後,把還有剩餘的那一條直接接上,最後回傳 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)本文採用