題目描述
給定兩個遞增排序的鏈表 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]
解題思路
此題目要求合併兩個遞增排序的鏈表，並且結果也保持遞增順序。由於鏈表本身是遞增排序的，處理過程中只需按照大小順序逐步拼接兩個鏈表即可。
主要的思路分為以下兩種方法：
- 使用迭代的方式遍歷兩個鏈表。
- 使用遞歸的方法合併兩個鏈表。
解法一：迭代法
思路
- 新建一個假頭節點（dummy node），用於存儲合併後的鏈表，並用一個指針（
current）來構建新鏈表。 - 遍歷
list1和list2： - 如果 list1 的當前節點值小於等於 list2 的當前節點值，則將 list1 的節點連接到 current，並移動 list1 的指針。
- 否則，將 list2 的節點連接到 current，並移動 list2 的指針。
- 移動 current 到新添加的節點。
- 當其中一個鏈表遍歷結束後，將另一個鏈表的剩餘部分直接連接到新鏈表的末尾。
- 返回假頭節點的下一個節點（即合併後的鏈表頭部）。
程式碼實現 (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)，僅使用了常數空間來存儲指針。
解法二：遞歸法
思路
- 如果
list1為空，直接返回list2，反之亦然。 - 比較
list1和list2當前節點的值： - 如果 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)，最壞情況下，遞歸深度等於兩個鏈表的節點總數，因此需要額外的遞歸堆疊空間。
總結
迭代法的優點是高效、使用常數額外空間，缺點是程式碼較多但清晰易懂；遞歸法的優點是簡潔、程式碼易於編寫和閱讀，缺點是可能導致遞歸堆疊溢出。
此題是一個經典的鏈表操作問題，非常適合用來練習遞歸與迭代的思路轉換。同時，由於它是排序合併的基礎問題，也可作為學習歸併排序的入門題目。