21 合并两个有序链表

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

示例：

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

解题思路分析

递归法

递归对于算法菜鸟来说就是属于那种一看就会，一用就废的。这里我提供一种递归的思路，先用正常人类的想法，去想遇到这类算法题，你本身想怎么解决，并从中一点一点进行归纳，找到递归点。

首先将两个升序链表合并为一个新的升序链表，对于人类来说，就是肉眼对链表中的元素，进行逐一比对，把小的元素放到前头。

比如：首先会比较L1[0]和L2[0]的大小，如果L1[0]小，那么先放入L1[0]；之后继续比较L1[1]和L2[0]的大小，依次类推，直到比完所有元素，就将整个链表返回。那么可以总结为，当L1[0] < L2[0]时，链表为 L1[0] + L1的剩余元素和L2进行比较的结果，那么假定有一个函数A，可以进行比较，那么可以整理为，L1[0] + A(L1[1:],L2)，如果L1[0] > L2[0]的话，就为L2[0] + A(L1,L2[1:])。

  L1[0] + A(L1[1:],L2)     L1[0] < L2[0]
  L2[0] + A(L1,L2[1:])     otherwise      

我们直接将以上递归过程建模，首先考虑边界情况。
特殊的，如果 l1 或者 l2 一开始就是 null ，那么没有任何操作需要合并，所以我们只需要返回非空链表。否则，我们要判断 l1 和 l2 哪一个的头元素更小，然后递归地决定下一个添加到结果里的值。如果两个链表都是空的，那么过程终止，所以递归过程最终一定会终止。

具体程序如下：

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元素少，我们可以将 l2 中的元素逐一插入 l1 中正确的位置。

算法

首先，我们设定一个哨兵节点 "prehead" ，这可以在最后让我们比较容易地返回合并后的链表。我们维护一个 prev 指针，我们需要做的是调整它的 next 指针。然后，我们重复以下过程，直到 l1 或者 l2 指向了 null ：如果 l1 当前位置的值小于等于 l2 ，我们就把 l1 的值接在 prev 节点的后面同时将 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) {
                //第一次循环时，也更改了prehead.next的引用
                prev.next = l1;
                l1 = l1.next;
            } else {
                //第一次循环时，也更改了prehead.next的引用
                prev.next = l2;
                l2 = l2.next;
            }
            //第一次循环时，更改了prev的引用，prehead保持不变，所以之后无论prev怎么变，都不会影响prehead和prehead.next
            prev = prev.next;
        }

        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }
}

对于这个程序有一点需要说明，ListNode prev = prehead将prev和prehead指向同一块内存，而while循环执行第一次时，更改了prev.next的值，同时也将更改prehead.next的值，指向L1或L2的第一个节点，这是为了之后prev更改指向地址时，可以记录链表的第一个节点，而链表这种数据结果，只要有了第一个节点，就可以通过xxx.next访问整个链表，而执行完比较之后，prev = prev.next，更改了prev指向的内存地址，但是并没有更改prehead的地址，所以之后无论prev和prev.next怎么变化，都不会影响prehead和prehead.next。