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