LeetCode 21: Merge Two Sorted Lists 詳細解析

題目描述

給定兩個已排序的鏈結串列 list1 和 list2 的頭節點。

將這兩個串列合併成一個已排序的串列。合併後的串列應該透過拼接前兩個串列的節點來建立。

返回合併後鏈結串列的頭節點。

範例

範例 1：

輸入：list1 = [1,2,4], list2 = [1,3,4]
輸出：[1,1,2,3,4,4]

範例 2：

輸入：list1 = [], list2 = []
輸出：[]

範例 3：

輸入：list1 = [], list2 = [0]
輸出：[0]

限制條件

• 兩個串列的節點數量範圍為 [0, 50]
• -100 <= Node.val <= 100
• list1 和 list2 都按照非遞減順序排列

解題思路

這道題目要求我們合併兩個已排序的鏈結串列。主要有兩種解法：

方法一：迭代法

使用雙指標的概念，逐一比較兩個串列的當前節點，將較小的節點加入結果串列。

核心概念：

1. 建立一個虛擬頭節點（dummy node）來簡化邊界條件處理
2. 使用一個指標追蹤結果串列的當前位置
3. 比較兩個串列的當前節點，選擇較小的加入結果
4. 處理剩餘的節點

方法二：遞迴法

利用遞迴的特性，每次選擇較小的節點，然後遞迴處理剩餘部分。

核心概念：

1. 基本情況：如果其中一個串列為空，返回另一個串列
2. 比較兩個串列的頭節點
3. 選擇較小的節點，並遞迴處理剩餘部分

程式碼實現

方法一：迭代法

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        # 建立虛擬頭節點
        dummy = ListNode(0)
        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
        if list2:
            current.next = list2
        
        # 返回真正的頭節點
        return dummy.next

方法二：遞迴法

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        # 基本情況
        if not list1:
            return list2
        if not list2:
            return list1
        
        # 比較並遞迴
        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2

複雜度分析

方法一：迭代法

• 時間複雜度：O(n + m)，其中 n 和 m 分別是兩個串列的長度
• 空間複雜度：O(1)，只使用了常數額外空間

方法二：遞迴法

• 時間複雜度：O(n + m)
• 空間複雜度：O(n + m)，遞迴調用堆疊的深度

詳細步驟說明

迭代法執行過程

以 list1 = [1,2,4] 和 list2 = [1,3,4] 為例：

初始狀態：
list1: 1 -> 2 -> 4
list2: 1 -> 3 -> 4
dummy: 0 -> null
current 指向 dummy

步驟 1：比較 1 和 1，選擇 list1 的 1
dummy: 0 -> 1
list1: 2 -> 4
list2: 1 -> 3 -> 4

步驟 2：比較 2 和 1，選擇 list2 的 1
dummy: 0 -> 1 -> 1
list1: 2 -> 4
list2: 3 -> 4

步驟 3：比較 2 和 3，選擇 list1 的 2
dummy: 0 -> 1 -> 1 -> 2
list1: 4
list2: 3 -> 4

步驟 4：比較 4 和 3，選擇 list2 的 3
dummy: 0 -> 1 -> 1 -> 2 -> 3
list1: 4
list2: 4

步驟 5：比較 4 和 4，選擇 list1 的 4
dummy: 0 -> 1 -> 1 -> 2 -> 3 -> 4
list1: null
list2: 4

步驟 6：list1 為空，將 list2 剩餘部分接上
結果：1 -> 1 -> 2 -> 3 -> 4 -> 4

進階思考

1. 為什麼使用虛擬頭節點？

虛擬頭節點（dummy node）可以簡化程式碼邏輯：

• 避免處理空串列的特殊情況
• 統一處理第一個節點和後續節點的邏輯
• 簡化返回值的處理

2. 遞迴 vs 迭代的選擇

• 遞迴法：程式碼簡潔優雅，但可能造成堆疊溢位
• 迭代法：空間效率更高，適合處理大型串列

3. 相關題目

• LeetCode 23: Merge k Sorted Lists
• LeetCode 148: Sort List
• LeetCode 88: Merge Sorted Array

總結

合併兩個已排序串列是鏈結串列操作的基礎題目。透過這道題，我們可以學習到：

1. 雙指標技巧在處理兩個序列時的應用
2. 虛擬頭節點簡化邊界條件的處理
3. 遞迴思維在解決分治問題時的優雅性

掌握這道題的解法，對於理解更複雜的鏈結串列操作和合併排序演算法都有很大幫助。

練習建議：

• 先自己實現迭代法，確保理解每個步驟
• 嘗試用遞迴法重寫，體會不同思維方式
• 思考如何擴展到合併 k 個已排序串列