📢前言

• 🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻
• 🌲 每天打卡一道算法題，既是一個(gè)學(xué)習(xí)過程，又是一個(gè)分享的過程😜
• 🌲 提示：本專欄解題 編程語言一律使用 C# 和 Java 兩種進(jìn)行解題
• 🌲 要保持一個(gè)每天都在學(xué)習(xí)的狀態(tài)，讓我們一起努力成為算法大神吧🧐！
• 🌲 今天是力扣算法題持續(xù)打卡第12天🎈！
• 🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻

🌲原題樣例

將兩個(gè)升序鏈表合并為一個(gè)新的 升序 鏈表并返回。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 兩個(gè)鏈表的節(jié)點(diǎn)數(shù)目范圍是 [0, 50]
• -100 <= Node.val <= 100
• l1 和 l2 均按 非遞減順序 排列

🌻C#方法一：遞歸

思路解析

我們可以如下遞歸地定義兩個(gè)鏈表里的 merge 操作（忽略邊界情況，比如空鏈表等）：

也就是說，兩個(gè)鏈表頭部值較小的一個(gè)節(jié)點(diǎn)與剩下元素的 merge 操作結(jié)果合并。

我們直接將以上遞歸過程建模，同時(shí)需要考慮邊界情況。

如果 l1 或者 l2 一開始就是空鏈表 ，那么沒有任何操作需要合并，所以我們只需要返回非空鏈表。

否則，我們要判斷 l1 和 l2 哪一個(gè)鏈表的頭節(jié)點(diǎn)的值更小，然后遞歸地決定下一個(gè)添加到結(jié)果里的節(jié)點(diǎn)。

如果兩個(gè)鏈表有一個(gè)為空，遞歸結(jié)束。

代碼：

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

執(zhí)行結(jié)果

通過
執(zhí)行用時(shí)：80 ms，在所有 C# 提交中擊敗了97.08%的用戶
內(nèi)存消耗：25.7 MB，在所有 C# 提交中擊敗了81.30%的用戶

復(fù)雜度分析

時(shí)間復(fù)雜度：O(n+m)
空間復(fù)雜度：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;
        }
    }
}

執(zhí)行結(jié)果

通過
執(zhí)行用時(shí)：0 ms，在所有 Java 提交中擊敗了100%的用戶
內(nèi)存消耗：37.6 MB，在所有 Java 提交中擊敗了89.42%的用戶

復(fù)雜度分析

時(shí)間復(fù)雜度：O(n+m)
空間復(fù)雜度：O((n+m)

🐢 遞歸 問題

但是使用遞歸有個(gè)問題很頭疼~

遞歸解法總是給人一種“只可意會(huì)不可言傳”的感覺，代碼一看就懂，自己動(dòng)手一寫就呆住了，很難受。

追溯原因的話，一是我們練習(xí)不夠，二是理解不夠。還是要多多練習(xí)加油才行呀！

函數(shù)在運(yùn)行時(shí)調(diào)用自己，這個(gè)函數(shù)就叫遞歸函數(shù)，調(diào)用的過程叫做遞歸。

比如定義函數(shù)f(x)=x+f(x?1)

💬總結(jié)

• 今天是力扣算法題打卡的第十二天！
• 文章采用 C# 和 Java 兩種編程語言進(jìn)行解題
• 有時(shí)候一些方法也是參考力扣大神寫的，也是邊學(xué)習(xí)邊分享，再次感謝算法大佬們
• 那今天的算法題分享到此結(jié)束啦，明天再見！