剑指 offer 25. 合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

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

限制：

• 0 <= 链表长度 <= 1000

解题思路：递归

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }
    if l1.Val > l2.Val {
        l1, l2 = l2, l1
    }
    l1.Next = mergeTwoLists(l1.Next, l2)
    return l1
}

• 时间复杂度：，其中 m 和 n 分别为两个链表的长度。因为每次递归都会去掉 l2 或 l1 的头节点，直到其中一个链表为空，因此，时间复杂度取决于合并后链表的长度，即 。
• 空间复杂度：，其中 m 和 n 分别为两个链表的长度。递归调用消耗的栈空间大小取决于递归调用的深度，递归执行次数为 m+n，因此，空间复杂度为 。