# 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 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。