https://leetcode-cn.com/problems/merge-two-sorted-lists/

原题

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：
image.png
输入：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 均按 非递减顺序 排列

题目分析

这道题最直接的想法就是链表比较，先创建出一个链表头，然后依次比较两条链表节点的大小。
如果 l1.val <= l2.val 时，prev.next 指向 l1，并且将 prev 指向新的节点 prev.next。反之亦然。
image.png

  1. const mergeTwoLists = (l1, l2) => {
  2.   const prehead = new ListNode(-1)
  4.   let pre = prehead
  5.   while(l1 && l2) {
  6.     if (l1.val <= l2.val) {
  7.       pre.next = l1
  8.       l1 = l1.next
  9.     } else {
  10.       pre.next = l2
  11.       l2 = l2.next
  12.     }
  13.     pre = pre.next
  14.   }
  16.   pre.next = l1 || l2
  17.   return prehead.next
  18. }

时间复杂度为：o(n + m)，其中 n 和 m 为两条链表的长度。空间复杂度为 o(1)。

看了题目分析，看到了这道题的另一个解法，就是递归。用公式来定义两个链表的 merge 操作：
image.png
代码如下：

  1. const mergeTwoLists = (l1, l2) => {
  2.   if (!l1) {
  3.     return l2
  4.   } else if (!l2) {
  5.     return l1
  6.   } else if (l1.val <= l2.val) {
  7.     l1.next = mergeTwoLists(l1.next, l2)
  8.     return l1
  9.   } else {
  10.     l2.next = mergeTwoLists(l2.next, l1)
  11.     return l2
  12.   }
  13. }

时间复杂度为：o(n + m)。
空间复杂度为 o(n + m)，递归调用 mergeTwoLists 函数时需要消耗栈空间，栈空间的大小取决于递归调用的深度。