Question

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

Answer 1

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

示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

我们可以递归地定义在两个链表上进行合并（merge）操作的结果，如下所示（在不考虑空列表的情况下）：

也就是说，我们取两个列表头部中较小的那个，然后再加上合并其余元素所得到的结果。

我们直接对上述递归建模，首先考虑边界情况。 具体来说，如果 l1 或 l2 最初为 null，则不需要执行合并，我们只需返回非空列表。否则，我们需要确定 l1 和 l2 中哪个的头节点更小，并递归地处理该头节点的 next 值以得到下一次合并结果。 如果两个列表都以空结束，那么递归就会停止。
​

我们完全可以通过迭代实现相同的思想，假设 l1 完全小于 l2，并逐个处理元素，在 l1 的必要位置插入 l2 元素。

首先，设置一个 prehead 节点（虚节点），这会帮助我们轻松地返回合并之后的列表的头节点。 我们还需要维护一个 prev 指针，它指向可能需要调整 next 指针的当前节点。 然后，执行以下操作，直到 l1 和 l2 中至少有一个指向 null：如果 l1 处的值小于或等于 l2 处的值，那么我们将 l1 连接到前一个节点，并递增 l1。 否则，我们对 l2 做同样的事情。 不管我们连接的是哪个列表，我们都会增加 prev，使它总是保持比我们的表头落后一步。

循环终止后，l1 和 l2 中最多有一个是非空的。 因此（因为输入列表是按有序的），如果其中一个列表是非空的，那么它包含的元素一定大于所有先前合并的元素。 这意味着我们可以直接将非空列表连接到已合并列表并返回它。