# 0021. 合并兩個有序鏈表 ## 題目地址(21. 合并兩個有序鏈表) <https://leetcode-cn.com/problems/merge-two-sorted-lists> ## 題目描述 ``` <pre class="calibre18">``` 將兩個升序鏈表合并為一個新的升序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。 示例： 輸入：1->2->4, 1->3->4 輸出：1->1->2->3->4->4 ``` ``` ## 前置知識 - [遞歸](https://github.com/azl397985856/leetcode/blob/master/thinkings/dynamic-programming.md) - [鏈表](https://github.com/azl397985856/leetcode/blob/master/thinkings/basic-data-structure.md) ## 公司 - 阿里 - 字節 - 騰訊 - amazon - apple - linkedin - microsoft ## 公司 - 阿里、字節、騰訊 ## 思路 使用遞歸來解題，將兩個鏈表頭部較小的一個與剩下的元素合并，并返回排好序的鏈表頭，當兩條鏈表中的一條為空時終止遞歸。 ## 關鍵點 - 掌握鏈表數據結構 - 考慮邊界情況 2 ## 代碼 - 語言支持：JS ``` <pre class="calibre18">``` <span class="hljs-title">/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */</span> <span class="hljs-title">/** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */</span> <span class="hljs-keyword">const</span> mergeTwoLists = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">l1, l2</span>) </span>{ <span class="hljs-keyword">if</span> (l1 === <span class="hljs-params">null</span>) { <span class="hljs-keyword">return</span> l2; } <span class="hljs-keyword">if</span> (l2 === <span class="hljs-params">null</span>) { <span class="hljs-keyword">return</span> l1; } <span class="hljs-keyword">if</span> (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); <span class="hljs-keyword">return</span> l1; } <span class="hljs-keyword">else</span> { l2.next = mergeTwoLists(l1, l2.next); <span class="hljs-keyword">return</span> l2; } }; ``` ``` **復雜度分析** M、N 是兩條鏈表 l1、l2 的長度 - 時間復雜度：O(M+N)O(M+N)O(M+N) - 空間復雜度：O(M+N)O(M+N)O(M+N) 大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。