跟着小蛋刷算法系列：合并两个有序链表 LeetCode 21题

题目描述

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

解题思路

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

非递归解法

首先自己实现一个单链表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，看下值的变化，一步一步跟踪，就能彻底理解了，在这里给大家出个思考题，如果是多个有序链表进行合并，我们应该怎么操作呢？关注我，下篇文章为你解答。