將兩個升序鏈表合并為一個新的 升序 鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。

輸入：l1 = [1,2,4], l2 = [1,3,4]
輸出：[1,1,2,3,4,4]
示例 2：

輸入：l1 = [], l2 = [] 輸出：[]
示例 3：

輸入：l1 = [], l2 = [0] 輸出：[0]

提示：

兩個鏈表的節點數目范圍是 [0, 50]
-100 <= Node.val <= 100 l1 和 l2 均按 非遞減順序 排列

方法一：
使用啞結點（dummy node）和雙指針來遍歷兩個鏈表，比較各自的節點值，將較小值的節點連接到新鏈表上，直至其中一個鏈表為空，最后將剩余部分直接接到新鏈表后面。

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:# 創建一個啞結點，方便返回結果鏈表dummy = ListNode(0)cur = dummy# 遍歷兩個鏈表，直到有一個為空while l1 and l2:if l1.val <= l2.val:cur.next = l1l1 = l1.nextelse:cur.next = l2l2 = l2.nextcur = cur.next# 將剩余部分接上cur.next = l1 if l1 else l2return dummy.next

代碼解析
1. 初始化啞結點：
創建一個啞結點 dummy 并用 cur 指向該節點，方便在不需要處理頭節點特殊情況的同時構造新的鏈表。
2. 雙指針遍歷：
使用 while l1 and l2 循環遍歷兩個鏈表。比較 l1 與 l2 當前節點的值，將較小的節點接到新鏈表的尾部，并移動對應鏈表的指針。
3. 接上剩余部分：
當其中一個鏈表遍歷完畢后，另一個鏈表可能還有剩余節點，直接將剩余部分接到新鏈表末尾即可。
4. 返回結果：
最后返回 dummy.next，即合并后鏈表的頭結點。

這種方法的時間復雜度為 O(n+m)，空間復雜度為 O(1)（不考慮輸出鏈表所需空間）。

方法二：
遞歸方法的核心思想是：比較兩個鏈表的頭節點，較小的那個作為合并后鏈表的頭，然后遞歸合并剩下的部分。

# 定義鏈表節點類
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:# 如果有一個鏈表為空，直接返回另一個鏈表if not l1:return l2if not l2:return l1# 遞歸調用時通過 self 調用類內的方法if l1.val <= l2.val:l1.next = self.mergeTwoLists(l1.next, l2)return l1else:l2.next = self.mergeTwoLists(l1, l2.next)return l2

代碼解析
1. 遞歸終止條件
如果 l1 為空，則直接返回 l2；如果 l2 為空，則返回 l1。這保證了當其中一個鏈表遍歷完時，遞歸能正確結束。
2. 遞歸比較
對于非空的 l1 和 l2，比較它們的值：
? 如果 l1.val 小于等于 l2.val，則將 l1 作為當前節點，并將 l1.next 指向遞歸合并后的結果。
? 否則，將 l2 作為當前節點，并將 l2.next 指向遞歸合并后的結果。
3. 返回結果
遞歸完成后，每一層調用都會返回合并后的鏈表頭，最終返回整個合并后的鏈表。

這種方法同樣能將兩個升序鏈表合并為一個新的升序鏈表，時間復雜度為 O(n+m)，但使用了遞歸來實現。