題目出處

21. Merge Two Sorted Lists

難度

easy

題目分類

Linked List, Recursion

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 就知道，我們只在乎這個基準點之後的事情。

個人範例程式碼

# 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 是個非常漂亮的做法，
可以快速把剩餘的內容提取出來。

Reference