题目描述

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

示例：

输入：1 -> 2 -> 4 ，1 -> 3 -> 4

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

方法 1：递归

思路

特殊的，如果 l1 或者 l2 一开始就是 null ，那么没有任何操作需要合并，所以我们只需要返回非空链表。

终止条件：两条链表分别名为 l1 和 l2，当 l1 为空或 l2 为空时结束

返回值：每一层调用都返回排序好的链表头

本级递归内容：如果 l1 的 val 值更小，则将 l1.next 与排序好的链表头相接，l2 同理
O( m + n )，m 为 l1 的长度，n 为 l2 的长度

代码实现

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //如果 l1 或者 l2 一开始就是 null ，说明不需要合并，所以我们只需要返回非空链表
        if(l1 == null) {
            return l2;
        }
        if(l2 == null) {
            return l1;
        }
        //如果11的val值更小，则将11.next与排序好的链表头相接，12同理
        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) {
        //先初始化一个预先指针 prehead，该指针的下一个节点指向真正的头结点head，是用来定位头结点的
        listnode prehead = new listnode(-1);
        listnode prev = prehead;
        //遍历列表l1和l2，直到全部遍历完毕
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                //prev.next始终指向比较之后的那个小的，l2同理
                prev.next = l1;
                //当前位置的l1后移一位
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }        //在循环终止的时候， l1 和 l2 至多有一个是非空的。
        //需要将非空链表接在合并链表的后面，并返回合并链表。
        prev.next = l1 == null ? l2 : l1;        return prehead.next;
    }
}