题目：

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

---

方法一：递归

函数在运行时调用自己，这个函数叫递归函数，调用的过程叫递归。

递归函数先不断调用自身，直到遇到终止条件后进行回溯，最终返回答案。

 如果L1.L2一开始为空链表，那么没有任何操作需要合并，只需要返回非空链表。否则要判断L1和l2哪一个链表的头节点的值更小，然后递归的决定下一个添加结果里的节点，如果两个链表有一个为空，递归结束。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        if list1 is None: #如果l1为空，说明不需要合并，直接返回 l2
            return list2
        elif list2 is None: #如果l2为空，说明不需要合并，直接返回 l1
            return list1
        elif list1.val<list2.val:#均不为空，如果l1的当前节点值小于l2的当前节点值，则将l1的当前节点作为合并后链表的头节点
            list1.next=self.mergeTwoLists(list1.next,list2) #合并 l1 的下一个节点和 l2
            return list1
        else:  #如果l1的当前节点值大于或等于l2的当前节点值，则将l2的当前节点作为合并后链表的头节点
            list2.next=self.mergeTwoLists(list2.next,list1) #合并 l1 和 l2 的下一个节点
            return list2

时间复杂度：O(m+n) n 和 m 分别为两个链表的长度,取决于合并后的链表长度.因为每次调用递归都会去掉 l1 或者 l2 的头节点（直到至少有一个链表为空），函数 mergeTwoList 至多只会递归调用每个节点一次.

空间复杂度：O(m+n) 

---

方法二：迭代

当l1和l2都不是空链表时，判l1和l2哪一个链表的头节点的值更小，将较小值得节点添加到结果里，当一个节点被添加到结果里之后，将对应链表中得节点向后移动一位。

设定一个prev指针，如果 l1 当前节点的值小于等于 l2 ，把 l1 当前的节点接在 prev 节点的后面同时将 l1 指针往后移一位。否则，对 l2 做同样的操作。不管将哪一个元素接在了后面，都需要把 prev 向后移一位

在终止循环的时候，l1和l2至多有一个是非空的。由于输入的两个链表都是有序的，所有不管哪个链表是非空的，它包含的所有元素都比前面已经合并链表中的所有元素都要大，所以，只需要简单地将非空链表接在合并链表地后面，并返回合并链表即可。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        prehead=ListNode(-1) #建一个虚拟头节点 prehead，其值为 -1
        pre=prehead #定义一个指针 prev，初始指向虚拟头节点
        while list1 and list2: #l1 和 l2 都不为空
            if list1.val<list2.val: #l1的当前节点值小于或等于l2当前节点值，将l1的当前节点链接到合并后的链表中
                pre.next=list1 #将 prev 的 next 指针指向 l1 的当前节点
                list1=list1.next #l1 指针移动到下一个节点
            else:
                pre.next=list2
                list2=list2.next
            pre=pre.next #将 prev 指针移动到合并后链表的最后一个节点
        pre.next = list1 if list1 is not None else list2#指针指向未合并完的链表
        return prehead.next  #prehead 是辅助节点，真正的链表头部是 prehead.next

时间复杂度：O(m+n)每次循环迭代中，l1 和 l2 只有一个元素会被放进合并链表中， 因此 while 循环的次数不会超过两个链表的长度之和

空间复杂度：O(1)需要常数的空间存放若干变量