LeetCode 解題思路：9. Merge Two Sorted Lists（合併兩個有序鏈表）

luk 收錄於 Leetcode

2024-12-09 約 800 字預計閱讀 4 分鐘

題目描述

給定兩個已排序的鏈結串列 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 都按照非遞減順序排列

核心概念：什麼是 head？

在深入解法之前，先理解一個重要概念：head（頭節點）。

鏈結串列結構：
head -> [1] -> [2] -> [3] -> [4] -> null
 ↑
這個就是 head（頭節點）

為什麼 head 很重要？

存取整個串列的唯一入口：在鏈結串列中，我們只能透過 head 來存取整個串列
代表整個串列：當題目說「返回合併後鏈結串列的頭節點」，就是要返回新串列的第一個節點

解法一：迭代法（使用虛擬頭節點）

什麼是 dummy node（虛擬頭節點）？

dummy node 是一個輔助節點，它的值不重要（通常設為 0），主要目的是簡化鏈結串列操作的邊界條件。

想像 dummy node 就像是：

建築工地的臨時圍欄：施工時需要，完工後要拆除
畫畫時的輔助線：幫助構圖，最後要擦掉
數學計算的草稿：過程需要，但不是最終答案

程式碼實現

# 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
        
        # 返回真正的頭節點（跳過 dummy）
        return dummy.next

視覺化執行過程

讓我們用圖解來理解為什麼要 return dummy.next：

初始狀態：
list1: 1 -> 2 -> 4
list2: 1 -> 3 -> 4

建立 dummy node：
dummy: [0] -> null
       ↑
    current

執行過程：
第一步：選擇 list1 的 1
dummy: [0] -> [1] -> [2] -> [4]
       ↑      ↑
    dummy   current

第二步：選擇 list2 的 1  
dummy: [0] -> [1] -> [1] -> [3] -> [4]
       ↑             ↑
    dummy         current

...繼續執行...

最終結果：
dummy: [0] -> [1] -> [1] -> [2] -> [3] -> [4] -> [4]
       ↑      ↑
    dummy   這才是真正合併後串列的開頭！

如果 return dummy：
[0] -> [1] -> [1] -> [2] -> [3] -> [4] -> [4]
 ↑
這個 0 是我們加的，不是原始資料！

如果 return dummy.next：
[1] -> [1] -> [2] -> [3] -> [4] -> [4]
 ↑
這才是正確的合併結果！

為什麼要用 dummy node？

沒有 dummy node 的寫法（複雜）

def mergeTwoLists(self, list1, list2):
    # 需要先處理空串列
    if not list1:
        return list2
    if not list2:
        return list1
    
    # 決定頭節點
    if list1.val <= list2.val:
        head = list1
        list1 = list1.next
    else:
        head = list2
        list2 = list2.next
    
    current = head
    
    # 繼續合併...
    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 head

dummy node 的優勢

統一處理：不需要特別處理第一個節點
簡化邊界條件：空串列的情況自然處理
程式碼更簡潔：邏輯更直觀，減少重複程式碼

複雜度分析

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

解法二：遞迴法

思路

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

程式碼實現

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

遞迴過程視覺化

mergeTwoLists([1,2,4], [1,3])
├─ 選擇 list1[0] = 1
├─ 1.next = mergeTwoLists([2,4], [1,3])
   ├─ 選擇 list2[0] = 1
   ├─ 1.next = mergeTwoLists([2,4], [3])
      ├─ 選擇 list1[0] = 2
      ├─ 2.next = mergeTwoLists([4], [3])
         ├─ 選擇 list2[0] = 3
         ├─ 3.next = mergeTwoLists([4], [])
            └─ 返回 [4]

最終結果：1 -> 1 -> 2 -> 3 -> 4

複雜度分析

時間複雜度：O(n + m)

每個節點都恰好被處理一次。

空間複雜度：O(n + m)

為什麼是 O(n + m)？讓我們詳細分析：

調用堆疊（Call Stack）視覺化：
┌─────────────────────────────┐
│ mergeTwoLists([4], [])      │ ← 第 5 層
├─────────────────────────────┤
│ mergeTwoLists([4], [3])     │ ← 第 4 層  
├─────────────────────────────┤
│ mergeTwoLists([2,4], [3])   │ ← 第 3 層
├─────────────────────────────┤
│ mergeTwoLists([2,4], [1,3]) │ ← 第 2 層
├─────────────────────────────┤
│ mergeTwoLists([1,2,4],[1,3])│ ← 第 1 層
└─────────────────────────────┘

每層儲存：

函數參數（list1 和 list2 指標）
返回地址
局部變數（如果有的話）

總共最多 n + m 層，每層 O(1) 空間，所以總空間複雜度是 O(n + m)。

兩種方法的比較

特性	迭代法	遞迴法
時間複雜度	O(n + m)	O(n + m)
空間複雜度	O(1)	O(n + m)
程式碼簡潔度	中等	高
理解難度	低	中等
適用場景	大型串列	小型串列

實用技巧總結

1. 鏈表操作的基本功

# 遍歷鏈表
current = head
while current:
    print(current.val)
    current = current.next

# 計算長度（沒有內建方法）
def get_length(head):
    length = 0
    current = head
    while current:
        length += 1
        current = current.next
    return length

2. dummy node 的應用場景

在串列開頭插入節點
刪除串列中的節點
合併多個串列
任何需要修改串列結構的操作

3. 選擇迭代還是遞迴？

選擇迭代：當處理大型資料或記憶體受限時
選擇遞迴：當追求程式碼簡潔或問題本身具有遞迴結構時

進階思考

1. 如何合併 k 個已排序串列？

這是 LeetCode 23 題，可以使用：

分治法
優先佇列（heap）
逐一合併

2. 如果不能修改原串列怎麼辦？

需要建立新節點而不是重用原有節點：

def mergeTwoListsCopy(self, list1, list2):
    dummy = ListNode(0)
    current = dummy
    
    while list1 and list2:
        if list1.val <= list2.val:
            current.next = ListNode(list1.val)  # 建立新節點
            list1 = list1.next
        else:
            current.next = ListNode(list2.val)  # 建立新節點
            list2 = list2.next
        current = current.next
    
    # 複製剩餘節點
    while list1:
        current.next = ListNode(list1.val)
        list1 = list1.next
        current = current.next
    
    while list2:
        current.next = ListNode(list2.val)
        list2 = list2.next
        current = current.next
    
    return dummy.next

總結

這道題看似簡單，但包含了許多重要概念：

虛擬頭節點（dummy node） 的巧妙運用
雙指標技巧 在處理兩個序列時的應用
遞迴思維 在解決分治問題時的優雅性
空間與時間的權衡 在演算法設計中的考量

掌握這些概念，不僅能解決這道題，更能為處理更複雜的鏈表問題打下堅實基礎！

練習建議

先手動模擬執行過程，理解 dummy node 的作用
嘗試不看答案實現兩種解法
思考如何處理三個已排序串列的合併
練習其他需要 dummy node 的鏈表題目