LeetCode-21. 合并两个有序链表(Java)

这是我在51CTO博客开启的写作之路，第一次正式写博客记录我在LeetCode的刷题日，希望能帮助更多的小伙伴攻面自己心仪的公司offer。

如下对于 LeetCode-21. 合并两个有序链表，进行全面解析并小结解题思路，同学们请参考：

1.题目描述

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 两个链表的节点数目范围是 [0, 50]
• -100 <= Node.val <= 100
• l1 和 l2 均按 非递减顺序 排列

2.思路分析

解题思路 ：链表、递归等

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

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

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

本级递归内容：如果 l1 的 val 值更小，则将 l1.next 与排序好的链表头相接，l2 同理 O(m+n)，m 为 l1的长度，n 为 l2 的长度。

3.算法实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) {
            return l2;
        }
        if(l2 == null) {
            return l1;
        }

        if(l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

如下是算法运行提交截图：

4.复杂度分析

时间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。因为每次循环迭代中，l1 和 l2 只有一个元素会被放进合并链表中， 因此 while 循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别的，因此总的时间复杂度为 O(n+m)。

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

5.小结

其实你们只需要把握一个技巧，就是准备一个虚拟头结点dummy，然后双指针指向list1和list2的表头对两个链表进行归并即可。