將兩個(gè)升序鏈表合并為一個(gè)新的 升序 鏈表并返回。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。

43.png

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

head = ListNode(0)
cur = head
while l1 and l2:
    if l1.val <=l2.val:
        cur.next = l1
        l1= l1.next
        cur =cur.next
    else:
        cur.next = l2
        l2 = l2.next
        cur =cur.next
if l1 :
    cur.next = l1
if l2 :
    cur.next = l2
return head.next

迭代法

if l1 is None:
        return l2
elif l2 is None:
        return l1
elif l1.val <= l2.val:
        l1.next = self.mergeTwoLists(l1.next, l2)
        return l1
else:
        l2.next = self.mergeTwoLists(l1, l2.next)
        return l2