07合并两个有序的链表

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

示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

递归函数必须要有终止条件，否则会出错；
递归函数先不断调用自身，直到遇到终止条件后进行回溯，最终返回答案。

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:  # 递归调用
            l1.next = self.mergeTwoLists(l1.next,l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1,l2.next)
            return l2

复杂度分析
给出一个递归算法，其时间复杂度O(T) 通常是递归调用的数量（记作 {R}R）和计算的时间复杂度的乘积（表示为O(s)）的乘积：O(T)=R∗O(s)

时间复杂度：O(m+n)
m,n为l1,l2的元素个数。递归函数每次去掉一个元素，直到两个链表都为空，因此需要调用R=O(m+n) 次。而在递归函数中我们只进行了 next 指针的赋值操作，复杂度为 O(1)，故递归的总时间复杂度为O(T)=R∗O(1)=O(m+n) 。

空间复杂度：O(m+n)。**
对于递归调用 self.mergeTwoLists()，当它遇到终止条件准备回溯时，已经递归调用了 m+n 次，使用了 m+n 个栈帧，故最后的空间复杂度为O(m+n)。

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

备注：在 Python 中，and 和 or 都有提前截至运算的功能。
and：如果 and 前面的表达式已经为 False，那么 and 之后的表达式将被跳过，返回左表达式结果
or：如果 or 前面的表达式已经为 True，那么 or 之后的表达式将被跳过，直接返回左表达式的结果

例子：[] and 7 等于 []

代码流程：（按行数）
判断 l1 或 l2 中是否有一个节点为空，如果存在，那么我们只需要把不为空的节点接到链表后面即可
对 l1 和 l2 重新赋值，使得 l1 指向比较小的那个节点对象
修改 l1 的 next 属性为递归函数返回值
返回 l1，注意：如果 l1 和 l2 同时为 None，此时递归停止返回 None

效率
时间复杂度：O(n)
空间复杂度：【考虑递归开栈】O(n)【不考虑】O(1)

来源：力扣（LeetCode）