合并两个有序链表【递归、迭代】

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

示例：
输入：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 循环运行的迭代次数等于这两个列表的长度之和。 所有其他的工作都不变，所以整体的复杂性是线性的。

• 空间复杂度：
  迭代方法只会分配几个指针，因此它的总体内存占用是恒定的。