題目：將兩個升序鏈表合並為一個新的 升序 鏈表並返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。
示例 1：
輸入：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 均按 非遞減順序 排列
程序說明：
方法一：先構建一個啞節點，作為新鏈表的head，不停遍歷並且比較list1和list2的節點值，然後按順序存入新鏈表裡。若後面出現其中一個list為空了，就直接將其後面的鏈表接入新鏈表後面即可。具體如圖：（ps：鏈表題目畫圖解決會是一個較好的方法）
方法二：會發現方法一需要開辟一個新的鏈表，這樣會使內存空間消耗增大，因此方法二用了遞歸的方法，直接在兩list中進行數值比較並連接。
全部代碼：
方法一：
# 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]:
phead = ListNode(0)
p = phead
while list1 and list2:
if list1.val <= list2.val:
p.next = list1
list1 = list1.next
else:
p.next = list2
list2 = list2.next
p = p.next
if list1 is not None:
p.next = list1
else:
p.next = list2
return phead.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]:
if list1 is None:
return list2
elif list2 is None:
return list1
elif list1.val < list2.val:
list1.next = self.mergeTwoLists(list1.next, list2)
return list1
else:
list2.next = self.mergeTwoLists(list1, list2.next)
return list2
題目來源：力扣（leetcode）
