问题21：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
第一次做这题的时候，我是先遍历两个链表，把它们的值存进同一个列表，对列表进行递增排序，再新创建一个链表，将排序后的值存进去。这种方法显然不满足题目要求，时间、空间复杂度都很高。
今天再做这题，发现这题其实也可以玩链表指针变换。
解法一：这个解法是网上看的，比较直观。设置一个dummy虚拟节点，并部署一个cur指针。然后遍历l1和l2。
（1）如果l1所指节点的值更小，cur指针指向l1，l1向后搜索一步；如果l2所指节点的值更小，cur指针指向l2，l2向后搜索一步；
（2）cur向后搜索一步；
（3）如果l1指向None，则cur直接指向l2，结束循环；如果l2指向None，则cur直接指向l1，结束循环；
（4）返回dummy.next。
完整代码：
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(0)
cur = dummy
while l1 and l2:
if l1.val < l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 or l2
return dummy.next
运行结果：
解法二：这个是我自己想的解法。思路是，把首节点的值较小的链表设为l1，作为基础链表；把首节点较大的链表设为l2，我们的目标是把l2中的所有值都填入l1的适当位置。具体看下面动画。
完整代码：
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1:
return l2
if not l2:
return l1
if l1.val > l2.val:
l3 = l1
l1 = l2
l2 = l3
#l1是首节点值较小的链表
#l2是首节点值较大的链表
head = l1
#将输出的head设为l1
while l2:
if l2.val >= l1.val and (not l1.next or l2.val < l1.next.val):
l3 = l1.next
l1.next = l2
l2 = l3
l1 = l1.next
return head
运行结果：
