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

中文：

將兩個(gè)有序鏈表合并為一個(gè)新的有序鏈表并返回。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。
示例：
輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4

因?yàn)閮商戽湵硎怯行虻模援?dāng)我們從左邊開始處理鏈表時(shí)，同一條鏈表上后面的值一定是比前面的值大的，所以，我們每次都選擇一個(gè)小的節(jié)點(diǎn)，將這個(gè)節(jié)點(diǎn)接到我們的head上，當(dāng)其中一條鏈表都空的時(shí)候我們把剩下的鏈表直接接在后面，退出循環(huán)。

我一開始寫的時(shí)候遇到了一個(gè)問題，我每次想處理兩個(gè)節(jié)點(diǎn)，但是它竟然給了：
輸入：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的第一個(gè)節(jié)點(diǎn)接在后面，但是在前面將l1大的情況，把兩個(gè)鏈表引用互換

# 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