Leetcode_21_合并两个有序链表_e

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

中文：

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

因为两天链表是有序的，所以当我们从左边开始处理链表时，同一条链表上后面的值一定是比前面的值大的，所以，我们每次都选择一个小的节点，将这个节点接到我们的head上，当其中一条链表都空的时候我们把剩下的链表直接接在后面，退出循环。

我一开始写的时候遇到了一个问题，我每次想处理两个节点，但是它竟然给了：
输入：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

前面我用过递归做，但是发现效率很低，所以改成了循环，循环和递归是可以互相转换的。一般情况下，递归的代码都很短。每次都把l1的第一个节点接在后面，但是在前面将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