题目描述

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

方法一：递归

（虽然但是，为什么要递归啊！谁想得到啊！）

(资料图片)

通过递归，找到不为null的链表头部值较小者

将剩余部分与另一个链表递归后链到后面

抄来的代码：

可以看到，有一个链表是null的情况下，直接return了非空链表

复杂度分析

时间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。因为每次调用递归都会去掉 l1 或者 l2 的头节点（直到至少有一个链表为空），函数 mergeTwoList 至多只会递归调用每个节点一次。因此，时间复杂度取决于合并后的链表长度，即O(n+m)。

空间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。递归调用 mergeTwoLists 函数时需要消耗栈空间，栈空间的大小取决于递归调用的深度。结束递归调用时 mergeTwoLists 函数最多调用 n+m 次，因此空间复杂度为 O(n+m)。

方法二：迭代

高大上的名字

其实就是每次把小的那个链到一个链表上

上代码：

时间复杂度不变，空间复杂度变为O(1)

踩的坑

这道题十分滴简单，但是，但是......

如果你调试的过程中出现了下面这种情况

就要注意了，看一看

有没有挪动输出链表的指针

输出链表的指针挪动是不是写到了分支条件里

大概，是这样的......