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

一、前言：

👨‍🎓作者：bug菌 ✏️博客：CSDN​、掘金等 💌公众号：​​猿圈奇妙屋​​ 🚫特别声明：原创不易，转载请附上原文出处链接和本文声明，谢谢配合。 🙏版权声明：文章里可能部分文字或者图片来源于互联网或者百度百科，如有侵权请联系bug菌处理。

二、题目描述：

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

具体请看如下示例：

示例 1:

LeetCode-21. 合并两个有序链表(java)_递归

输入：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​​ 均按 非递减顺序 排列

题目来源：​​LeetCode官网​​题目难度：⭐⭐⭐

三、思路分析：

       这题上升到了链表结构，不知道有多少小伙伴熟悉它，不过解这道题还是挺简单的。合并两个顺序链表，无非就可以采用递归过程建模。

       根据以上规律考虑本题目， 终止条件：当两个链表都为空时，表示我们对链表已合并完成。 

       如何递归？我们直接判断 l1 和 l2 头结点哪个更小，然后较小结点的 next 指针指向其余结点的合并结果。也就是说，两个链表头部值较小的一个节点与剩下元素的 ​​merge​​ 操作结果合并即可。

部分图片演示：

LeetCode-21. 合并两个有序链表(java)_递归_02

LeetCode-21. 合并两个有序链表(java)_升序_03

四、算法实现：

递归法_AC代码

具体算法代码实现如下：

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;
         }
     }
 }

五、总结：

递归法之leetcode提交运行结果截图如下：

LeetCode-21. 合并两个有序链表(java)_升序_04

复杂度分析：

• 时间复杂度：O(n+m)。其中n 和m 分别为两个链表的长度。
• 空间复杂度：O(n + m)。其中n 和m 分别为两个链表的长度。

       还有一点很关键啊，就是如果两个链表有一个为空，则递归结束即可。

       再者，解题道路千万条，小伙伴们，如果你们有啥更好的想法或者思路，欢迎评论区告诉我哦，大家一起互相借鉴互相学习，方能成长的更快。

       好啦，以上就是本期的所有内容啦，咱们下期见咯。