千淘万漉虽辛苦，吹尽狂沙始到金。

题目

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

示例1

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例2

输入：l1 = [], l2 = []
输出：[]

示例3

输入：l1 = [], l2 = [0]
输出：[0]

提示

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

题解

保底法

如果对链表不熟悉的人可以使用笨拙方法，就是把链表的数据取出存放在数组中，然后合并这两个有序数组，最后根据合并后到数组创建新到链表即可。

我称这种笨拙的方法为保底法，至少能提交一版代码。

合并两个有序数组，对于前端人员来说方法很多：

1. 使用解构合并

let arr1 = [1,2,4];
let arr2 = [1,3,4];
let arr = [...arr1, ...arr2].sort();

2. concat 方法

arr1.concat(arr2).sort();

3. for 循环

for (let i = 0; i < arr2.length; i++) {
    arr1.push(arr2[i);
}
arr1.sort();

4. 使用 push(...arr)

arr1.push(...arr2);
arr1.sort();

5. push 组合 apply 方法

arr1.push.apply(arr1, arr2);
arr1.sort();

6. 归并算法合并

迭代法

根据归并算法思想，从两个链表到头节点开始对比，哪个节点的值小，就把节点的指针向后移动，然后接着对比两个节点的值，这样迭代下去即可。

我们首先建一个空的链表，每次对比值小的节点赋值给新建链表的 next 指针。

只要有一个链表遍历完毕，就结束循环。

结束循环后，可能出现三种情况:

1. 两个链表正好都遍历完，此时后续不需要做任何操作
2. 只有第一个链表遍历完，此时需要把第二个链表的节点直接赋值给新建链表的 next指针
3. 只有第二个链表遍历完，此时需要把第一个链表的节点直接赋值给新建链表的 next 指针

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function(list1, list2) {
    if (!list1) {
        return list2;
    }
    if (!list2) {
        return list1;
    }

    // 新建一个链表
    let list = new ListNode();
    // list的指针会移动，保存它的头指针，最后返回它的 next即可
    let retList = list;
    // list1 和 list2 都不是null 时才需要遍历
    while(list1 && list2) {
        // 对比两个节点的大小，把小的节点赋值给 list
        if (list1.val >= list2.val) {
            list.next = list2;
            // 指针向后移动一位
            list2 = list2.next;
        } else {
            list.next = list1;
            // 指针向后移动一位
            list1 = list1.next;
        }
        list = list.next;
    }
    // 遍历完后，哪个链表存在就把剩下的链表连接到list后面即可
    if (list1) {
        list.next = list1;
    } else if (list2) {
        list.next = list2;
    }
    return retList.next;
};

运行结果:

算法复杂度

• 时间复杂度：O(m + n) 每次循环迭代只有一个节点被合并进新链表中，循环的最坏情况就是两个链表的节点都循环遍历一遍，也就是 m + n 次。

• 空间复杂度: O(1) 我们只是创建了一个节点作为合并后新链表的开头节点，其他的并没有开辟多余的空间。

递归法

两个有序链表，我们以 l1 = [1, 3], l2 = [2, 4] 为例。

首先对比第一个节点，1 比 2 小，我们就把 l1.next 指向 l2。下一轮对比就是 l1 = [3], l2 = [1, 2, 4] 的对比。

每轮结束都是一个新的排序链表与另一个链表的对比。

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function(list1, list2) {
    if (!list1) {
        return list2;
    }
    if (!list2) {
        return list1;
    }
    if(list1.val < list2.val) {
        // list1.next 指向合并后的排序链表
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    }
    list2.next = mergeTwoLists(list2.next, list1);
    return list2;
};

运行结果:

算法复杂度

• 时间复杂度：O(m + n) 递归次数最多 m + n 次。

• 空间复杂度: O(m + n) 递归调用会消耗栈空间，大小取决于递归的深度。最大深度就是 m + n。