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
