【合并两个有序链表】
合并两个有序链表
- 一、题目
- 二、递归解法
- 三、迭代解法
一、题目
二、递归解法
思路：我们可以如下递归地定义两个链表里的 merge 操作（忽略边界情况，比如空链表等）：
如果链表1的第一个元素比链表2的第一个元素小，那么结果链表的第一个元素就是链表1的第一个元素，然后继续合并链表1的剩余部分和整个链表2。
如果链表2的第一个元素更小或者相等，那么结果链表的第一个元素就是链表2的第一个元素，然后继续合并链表1的整个部分和链表2的剩余部分。
时间复杂度：O(n+m)
空间复杂度：O(n+m)
三、迭代解法
思路:我们可以用迭代的方法来实现上述算法。当 l1 和 l2 都不是空链表时，判断 l1 和 l2 哪一个链表的头节点的值更小，将较小值的节点添加到结果里，当一个节点被添加到结果里之后，将对应链表中的节点向后移一位。
时间复杂度：O(n+m)
空间复杂度：O(1)
