合并两个有序链表（八）

一、题目描述

这是 LeetCode 热题 HOT 100 上第二十一题：合并两个有序链表，难度为 简单。

Tag：「链表」、「递归」

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

示例 1：

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

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

1、两个链表的节点数目范围是 [0, 50]

2、-100 <= Node.val <= 100

3、l1 和 l2 均按 非递减顺序 排列

二、解题思路

1、这道题可以使用递归实现，新链表也不需要构造新节点，我们下面列举递归三个要素

2、终止条件：两条链表分别名为 l1 和 l2，当 l1 为空或 l2 为空时结束

3、返回值：每一层调用都返回排序好的链表头

4、本级递归内容：如果 l1 的 val 值更小，则将 l1.next 与排序好的链表头相接，l2 同理

代码实现：

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        else if (l2 == null) {
            return l1;
        }
        else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
        else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }

    }
}

时间复杂度和空间复杂度分析：

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

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

三、总结

本道算法题难度简单，主要考察了我们对链表和递归的掌握，关于递归我们应该做到以下两点：

1、递归函数必须要有终止条件，否则会出错

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

好了，本篇文章到这里就结束了，感谢你的阅读🤝