個人範例程式碼 - 二刷 (2026/08/05)

# 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

        dummy = tail = ListNode()
        while list1 and list2:
            if list1.val < list2.val:
                tail.next = list1
                list1 = list1.next
            else:
                tail.next = list2
                list2 = list2.next

            tail = tail.next

        tail.next = list1 or list2

        return dummy.next # First is None

算法說明

一個經常困住的地方：操作 linked list 時會擔心後續的改動，破壞前面已經操作的內容。
實際上並不會：

1. 移動 tail.next 指向下一個目標 node (list1 or list2 較小的值)
2. list1 or list2 移動
3. 移動 tail = tail.next

最後收尾小技巧：使用 list1 or list2 (因為一個已經走到尾巴，只會剩另外一個)

Time Complexity

O(n+m) # 兩個 Linked list 走完

Space Complexity

O(1) # 只有 inplace 改動

Boundary conditions

留意幾個測資

1. [] []
2. [] [0]
3. [0] []

註：其實沒有前面那一小段 if 判斷，直接進 while 也能處理

Linked List 操作 (for 新手教學)

新手如我，最不熟悉 Linked List 的操作，剛好網路上有其他大神分享，
我們來簡單的重新敘述一下他教學的內容：

參考：Python3 Solution with a Detailed Explanation - dummy explained

pointer 跟著移動?

假設我們定義一個 head = temp = ListNode(0)，
(這樣寫太難懂的話，請理解為 temp = ListNode(0)， head = temp)

在 Linked List 操作中可能最讓人困惑的就是，當我們去移動 temp 時，head 會不會跟著移動?
在 python 裡面，我們進行 temp = temp.next 的動作，
實際上我們只有移動 「temp 指向的位置」，我們可以理解「temp.next」在此只是一個「位置的代稱」，
就像我們說
b = 1
a = b
b = 2
最後會知道 a = 1, b = 2 而不是 a, b = 2，

不要像作者我在一開始因為開始有點複雜，就被搞亂了。

好啊，那 pointer 不移動，為啥 temp 去改能影響到 head?

head 一開始指到的記憶體位置與 temp 是相同的，
而我們控制 temp 在此點的指向，因此 head 確實可以從這個記憶體位置往下找。

比喻

我們可以想像我們現在正在挖金礦，我們順著 線索 1 -> 2 -> 3 不斷往前，
但我們如果要告訴後來的人這條路該怎麼走，我們是必要紀錄起始點的位置。
因此這裡就會分為 head, temp， head 幫助我們保留起始位置，而 temp 負責幫我們移動。
中間的每一個線索都已經由 temp 在過程中建立好正確連結，
因此 head 尋著 temp 打通的道路再走一次，就是走 temp 開過的路。

ListNode(0)? return head.next

不用想那麼多，這只是建立一個供我們參考的基準點。
從我們最後 return head.next 就知道，我們只在乎這個基準點之後的事情。

個人範例程式碼 - 一刷 (2022/03/05)

# 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]:
        head = temp = ListNode(0)
        while list1 and list2: 
            if list1.val < list2.val:
                temp.next = list1 # ans next Node
                list1 = list1.next
            else:
                temp.next = list2 # ans next Node
                list2 = list2.next # move next
            temp = temp.next # ans move next
        temp.next = list1 or list2 # remain things
        return head.next

Time Complexity

O(m+n)

Space Complexity

O(1)

算法說明

如上面介紹所述

corner case 特殊情況處理

注意沒有值的情況，例如開頭就沒有的時候

Boundary conditions/ Edge conditions 邊際情況處理

終止條件

注意沒有值的情況，
我們大原則是每次都會檢查「this Node 是否為 None」再開始接續動作。

提取剩餘內容

另外最後的 list1 or list2 是個非常漂亮的做法，
可以快速把剩餘的內容提取出來。