题目描述

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

解题思路

按照题目的描述，给定的两个链表各自本身是有序的，我们要将它合并成一个有序链表，也就是要把这两个链表合到一起重新排序得到最终的结果，这道题我提供了两种解法，非递归解法和递归解法。

非递归解法

首先自己实现一个单链表ListNode：

public class ListNode<E> {    public ListNode next;    public E e;    public ListNode(E e) {        this(e, null);    }​    public ListNode(E e, ListNode next) {        this.e = e;        this.next = next;    }​​    public ListNode() {        this(null, null);    }复制代码

非递归代码

 ​public class MergeList {    public static void main(String[] args) {        MergeList mergeList = new MergeList();        ListNode node1 = new ListNode(1);        ListNode node11 = new ListNode(3)；        node1.next = node11;        node11.next = node111;        ListNode node2 = new ListNode(2);        ListNode node22 = new ListNode(4);        ListNode node222 = new ListNode(6);        node2.next = node22;        node22.next = node222;        ListNode node = mergeList.mergeTwoLists(node1, node2);    }​    public ListNode mergeTwoLists(ListNode<Integer> l1, ListNode<Integer> l2) {        //设置虚拟头节点        ListNode<Integer> dummy = new ListNode<Integer>(0), pp = dummy;        while (l1 != null && l2 != null) {            if (l1.e <= l2.e) {                pp.next = l1;                pp = pp.next;                l1 = l1.next;            } else {                pp.next = l2;                pp = pp.next;                l2 = l2.next;            }        }        if (l1 != null) {            pp.next = l1;        }        if (l2 != null) {            pp.next = l2;        }        return dummy.next;    }}​复制代码

非递归解法总体思路就是通过 while 循环对 l1 和 l2 链表的值进行一一比较，假设第一轮比较 l1 的值是最小的，就将 l1 放入结果链表中，然后对 l1 进行移动到下一位，两者继续比较，依次类推，直到 l1 , l2 其中一方为空，跳出循环，跳出循环后因为两者肯定有一方还有值，直接将当前结果链表节点的next节点指向不为空的链表，最终就得到了排序后的结果，进行返回。

通过动态图来进行演示：

递归解法

   /**     * 递归解法     *     * @param l1     * @param l2     * @return     */    public ListNode mergeTwoLists(ListNode<Integer> l1, ListNode<Integer> l2) {        if (l1 == null) {            return l2;        } else if (l2 == null) {            return l1;        } else if (l1.e < l2.e) {            l1.next = mergeTwoList(l1.next, l2);            return l1;        } else {            l2.next = mergeTwoList(l1, l2.next);            return l2;        }​    }复制代码

递归的终止条件就是两个链表 l1 , l2 其中有一个为空时就终止然后往上回溯，最终返回答案。

那怎么去递归的呢？

我们判断 l1 和 l2 头节点哪个更小，然后将较小节点的 next 指针指向其余节点的合并结果,就是继续调用递归方法，直到满足终止条件。

递归代码非常简洁，但是可能看起来很绕，一层一层的递归，一不小心就容易绕晕了，我们来把这个递归进行解剖，一步一步进行分析：

l1是1->3, l2 是 2->4->6

第一次方法调用：

l1 的头节点是1，l2 是3，所以会将 l1.next 指向下次的方法调用

此时：结果链表为：l1->l1.next=mergeTwoList

  l1.next = mergeTwoList(l1.next, l2);            return l1;复制代码

第二次方法调用：

将l1的第二个节点和l2的头节点进行比较

3比2大，所以l1.next就是 l2 的头节点

 l2.next = mergeTwoList(l1, l2.next);            return l2;复制代码

结果链表： 继续顺延为：l1 -> l2-> l2.next=mergeTwoList

第三次方法调用： 就是 l2 的第二个节点和 l1 的第二个节点进行比较：

4比3大，因此l2的next节点就要l1的第二个节点

结果链表： l1-> l2->l1.next->l1.next.next = mergeTwoList

第四次方法调用：

此时l1没有第三个节点，所以l1当前节点为空,开始往上回溯：

因此 l1的空节点 就是l2的第二个节点

结果链表： l1-> l2 -> l1.next -> l2.next

那么最终结果值就为：1->2->3->4->6

总结

两种解法，可能第二种递归解法比较难以理解，我的建议是一步一步debug，看下值的变化，一步一步跟踪，就能彻底理解了，在这里给大家出个思考题，如果是多个有序链表进行合并，我们应该怎么操作呢？关注我，下篇文章为你解答。