📢前言
🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻
🌲 每天打卡一道算法题，既是一个学习过程，又是一个分享的过程😜
🌲 提示：本专栏解题 编程语言一律使用 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 两种编程语言进行解题
有时候一些方法也是参考力扣大神写的，也是边学习边分享，再次感谢算法大佬们
那今天的算法题分享到此结束啦，明天再见！
