📢前言
- 🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻
- 🌲 每天打卡一道算法题，既是一个学习过程，又是一个分享的过程😜
- 🌲 提示：本专栏解题 编程语言一律使用 C# 和 Java 两种进行解题
- 🌲 要保持一个每天都在学习的状态，让我们一起努力成为算法大神吧🧐！
- 🌲 今天是力扣算法题持续打卡第12天🎈！
- 🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻
🌲原题样例
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 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 均按
非递减顺序 排列
🌻C#方法一：递归
思路解析
我们可以如下递归地定义两个链表里的 merge 操作（忽略边界情况，比如空链表等）：
也就是说，两个链表头部值较小的一个节点与剩下元素的 merge 操作结果合并。
我们直接将以上递归过程建模，同时需要考虑边界情况。
如果 l1 或者 l2 一开始就是空链表 ，那么没有任何操作需要合并，所以我们只需要返回非空链表。
否则，我们要判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。
如果两个链表有一个为空，递归结束。
代码：
public 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;
}
}
}
执行结果
通过
执行用时：80 ms，在所有 C# 提交中击败了97.08%的用户
内存消耗：25.7 MB，在所有 C# 提交中击败了81.30%的用户
复杂度分析
时间复杂度：O(n+m)
空间复杂度：O((n+m)
🌻Java 方法一：递归
思路解析
该解题方法与C#思路一致，代码有所不同
代码
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;
}
}
}
执行结果
通过
执行用时：0 ms，在所有 Java 提交中击败了100%的用户
内存消耗：37.6 MB，在所有 Java 提交中击败了89.42%的用户
复杂度分析
时间复杂度：O(n+m)
空间复杂度：O((n+m)
🐢 递归 问题
但是使用递归有个问题很头疼~
递归解法总是给人一种“只可意会不可言传”的感觉，代码一看就懂，自己动手一写就呆住了，很难受。
追溯原因的话，一是我们练习不够，二是理解不够。还是要多多练习加油才行呀！
函数在运行时调用自己，这个函数就叫递归函数，调用的过程叫做递归。
比如定义函数f(x)=x+f(x−1)
💬总结
- 今天是力扣算法题打卡的第十二天！
- 文章采用 C# 和 Java 两种编程语言进行解题
- 有时候一些方法也是参考力扣大神写的，也是边学习边分享，再次感谢算法大佬们
- 那今天的算法题分享到此结束啦，明天再见！
