将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
方法一：递归
思路
我们可以递归地定义在两个链表上进行合并（merge）操作的结果，如下所示（在不考虑空列表的情况下）：
也就是说，我们取两个列表头部中较小的那个，然后再加上合并其余元素所得到的结果。
算法
我们直接对上述递归建模，首先考虑边界情况。 具体来说，如果 l1 或 l2 最初为 null，则不需要执行合并，我们只需返回非空列表。否则，我们需要确定 l1 和 l2 中哪个的头节点更小，并递归地处理该头节点的 next 值以得到下一次合并结果。 如果两个列表都以空结束，那么递归就会停止。
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
else if (l2 == null) {
return l1;
}
else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}
else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
复杂度分析
-
时间复杂度：
因为每次递归调用都会将指向 l1 或 l2 的指针递增一次（逐渐接近每个列表末尾的 null），所以每个列表中的每个元素都会对 mergeTwoLists 进行一次调用。 因此，时间复杂度与两个列表的大小之和是线性相关的。 -
空间复杂度：
一旦调用 mergetwolist，直到到达 l1 或 l2 的末尾时才会返回，因此的栈将会消耗
的空间。
方法二：迭代
思路
我们完全可以通过迭代实现相同的思想，假设 l1 完全小于 l2，并逐个处理元素，在 l1 的必要位置插入 l2 元素。
算法
首先，设置一个 prehead 节点（虚节点），这会帮助我们轻松地返回合并之后的列表的头节点。 我们还需要维护一个 prev 指针，它指向可能需要调整 next 指针的当前节点。 然后，执行以下操作，直到 l1 和 l2 中至少有一个指向 null：如果 l1 处的值小于或等于 l2 处的值，那么我们将 l1 连接到前一个节点，并递增 l1。 否则，我们对 l2 做同样的事情。 不管我们连接的是哪个列表，我们都会增加 prev，使它总是保持比我们的表头落后一步。
循环终止后，l1 和 l2 中最多有一个是非空的。 因此（因为输入列表是按有序的），如果其中一个列表是非空的，那么它包含的元素一定大于所有先前合并的元素。 这意味着我们可以直接将非空列表连接到已合并列表并返回它。
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// maintain an unchanging reference to node ahead of the return node.
ListNode prehead = new ListNode(-1);
ListNode prev = prehead;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
prev.next = l1;
l1 = l1.next;
} else {
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
// exactly one of l1 and l2 can be non-null at this point, so connect
// the non-null list to the end of the merged list.
prev.next = l1 == null ? l2 : l1;
return prehead.next;
}
}
复杂度分析
-
时间复杂度：
在每次循环迭代中， l1 和 l2 其中之一会递增，所以 while 循环运行的迭代次数等于这两个列表的长度之和。 所有其他的工作都不变，所以整体的复杂性是线性的。 -
空间复杂度：
迭代方法只会分配几个指针，因此它的总体内存占用是恒定的。
网友评论