English：
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
中文：
將兩個有序鏈表合并為一個新的有序鏈表并返回烁竭。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的衅鹿。
示例：
輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4
因為兩天鏈表是有序的寂拆，所以當(dāng)我們從左邊開始處理鏈表時，同一條鏈表上后面的值一定是比前面的值大的夭坪，所以，我們每次都選擇一個小的節(jié)點淋袖，將這個節(jié)點接到我們的head上婴削，當(dāng)其中一條鏈表都空的時候我們把剩下的鏈表直接接在后面，退出循環(huán)隙券。
我一開始寫的時候遇到了一個問題男应，我每次想處理兩個節(jié)點，但是它竟然給了：
輸入：5, 1->3->4
這么一種輸入娱仔。沐飘。。
后來看了題解才想起來牲迫。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1:
return l2
if not l2:
return l1
head = ListNode(None)
cur = head
while l1 or l2:
if not l1:
cur.next = l2
break
if not l2:
cur.next = l1
break
if l1.val < l2.val:
min = l1
l1 = l1.next
else:
min = l2
l2 = l2.next
cur.next = min
cur = cur.next
return head.next
前面我用過遞歸做耐朴，但是發(fā)現(xiàn)效率很低，所以改成了循環(huán)盹憎，循環(huán)和遞歸是可以互相轉(zhuǎn)換的筛峭。一般情況下，遞歸的代碼都很短陪每。每次都把l1的第一個節(jié)點接在后面影晓，但是在前面將l1大的情況，把兩個鏈表引用互換
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if l1 and l2:
if l1.val > l2.val: l1, l2 = l2, l1
l1.next = self.mergeTwoLists(l1.next, l2)
return l1 or l2
