[LeetCode解題攻略] 21. Merge Two Sorted Lists

題目描述

給定兩個遞增排序的鏈表 list1 和 list2，將它們合併為一個新的 遞增排序 的鏈表，並返回這個新鏈表。新的鏈表應該由這兩個鏈表中的節點組成，而不應創建新的節點。最後回傳合併後的鍊錶的頭節點。

範例 1：

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

範例 2：

Input: list1 = [], list2 = []
Output: []

範例 3：

Input: list1 = [], list2 = [0]
Output: [0]

解題思路

此題目要求合併兩個遞增排序的鏈表，並且結果也保持遞增順序。由於鏈表本身是遞增排序的，處理過程中只需按照大小順序逐步拼接兩個鏈表即可。

主要的思路分為以下兩種方法：

1. 使用迭代的方式遍歷兩個鏈表。
2. 使用遞歸的方法合併兩個鏈表。

解法一：迭代法

思路

1. 新建一個假頭節點（dummy node），用於存儲合併後的鏈表，並用一個指針（current）來構建新鏈表。
2. 遍歷 list1 和 list2：
3. • 如果 list1 的當前節點值小於等於 list2 的當前節點值，則將 list1 的節點連接到 current，並移動 list1 的指針。
   • 否則，將 list2 的節點連接到 current，並移動 list2 的指針。
   • 移動 current 到新添加的節點。
3. 當其中一個鏈表遍歷結束後，將另一個鏈表的剩餘部分直接連接到新鏈表的末尾。
4. 返回假頭節點的下一個節點（即合併後的鏈表頭部）。

程式碼實現 (Python)

# 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(-1)
        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 if list1 else list2

        # 返回合併後的鏈表
        return dummy.next

時間與空間複雜度

• 時間複雜度：O(m + n)，其中 m 和 n 分別是 list1 和 list2 的長度。我們需要遍歷兩個鏈表的所有節點。
• 空間複雜度：O(1)，僅使用了常數空間來存儲指針。

解法二：遞歸法

思路

1. 如果 list1 為空，直接返回 list2，反之亦然。
2. 比較 list1 和 list2 當前節點的值：
3. • 如果 list1 的值小於等於 list2 的值，則 list1 的下一個節點接上 mergeTwoLists(list1.next, list2)，並返回 list1；
   • 否則，list2 的下一個節點接上 mergeTwoLists(list1, list2.next)，並返回 list2。

程式碼實現 (Python)

# 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]:
        # 如果其中一個鏈表為空，直接返回另一個
        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(m + n)，與迭代法相同，因為每個節點都會被訪問一次。
• 空間複雜度：O(m + n)，最壞情況下，遞歸深度等於兩個鏈表的節點總數，因此需要額外的遞歸堆疊空間。

總結

迭代法的優點是高效、使用常數額外空間，缺點是程式碼較多但清晰易懂；遞歸法的優點是簡潔、程式碼易於編寫和閱讀，缺點是可能導致遞歸堆疊溢出。

此題是一個經典的鏈表操作問題，非常適合用來練習遞歸與迭代的思路轉換。同時，由於它是排序合併的基礎問題，也可作為學習歸併排序的入門題目。