LeetCode-21-合并两个有序链表

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

示例：

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

准备工作

定义链表结点：

function ListNode(val) {
    this.val = val;
    this.next = null;
}

数组转链表，方便测试数据的输入：

function arrayToList(array) {
    let node = null;
    for (let i = array.length - 1; i >= 0; i --) {
        let newNode = new ListNode(array[i]);
        newNode.next = node;
        node = newNode;
    }
    return node;
}

链表转字符串，方便测试结果的显示：

function listToString(node) {
    return node ? `${node.val}${node.next ? ` -> ${listToString(node.next)}` : '' }` : null;
}

递归算法

链表的合并可以比较容易写成递归的形式，如果不考虑边界情况，合并两个链表只需要将两个表头中较小的一个作为新的表头，剩下的部分递归合并即可：

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
const mergeTwoLists1 = function(l1, l2) {
    // 边界情况，两个链表中有一个为空，则返回另一个链表
    if (!l1) {
        return l2;
    }
    if (!l2) {
        return l1;
    }
    // 都不为空，则比较两个表头的值，将较小的作为新的表头，其它的结点再递归合并
    if (l1.val < l2.val) {
        l1.next = mergeTwoLists1(l1.next, l2);
        return l1;
    }
    l2.next = mergeTwoLists1(l1, l2.next);
    return l2;
};

测试：

let start = new Date();
const test = mergeTwoLists1;
console.log(listToString(test(arrayToList([1, 2, 4]), arrayToList([1, 3, 4])))); // 1 -> 1 -> 2 -> 3 -> 4 -> 4
console.log(new Date().getTime() - start.getTime()); // 3

时间复杂度： 每次递归会合并两个链表中的一个表头，所以时间复杂度为O(m+n)，m和n分别为两个链表的长度
空间复杂度： 最差情况下链表的每个结点都递归一次，共有m+n个栈，所有空间复杂度为O(m+n)

迭代

上面的递归的效率不太高，空间占用也很严重，我们可以改写成非递归的形式。

定义一个新链表，新链表的尾结点始终指向两个链表头结点中值较小的一个，并将该链表的头结点后移，这样就可以将两个链表合并起来了：

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
const mergeTwoLists2 = function(l1, l2) {
    let preHead = new ListNode(null); // 定义一个头结点之前的结点，方便最后的输出
    let last = preHead; // 新链表的尾结点
    while (l1 && l2) {
        // 两链表都不为空时，尾结点的next指向值较小的结点，同时将该链表的指针后移
        if (l1.val < l2.val) {
            last.next = l1;
            l1 = l1.next;
        } else {
            last.next = l2;
            l2 = l2.next;
        }
        // 尾结点后移
        last = last.next;
    }
    // 尾结点指向剩下不为空的结点
    last.next = l1 || l2;
    return preHead.next;
};

测试：

let start = new Date();
const test = mergeTwoLists2;
console.log(listToString(test(arrayToList([1, 2, 4]), arrayToList([1, 3, 4])))); // 1 -> 1 -> 2 -> 3 -> 4 -> 4
console.log(new Date().getTime() - start.getTime()); // 2

时间复杂度： 最差情况下两个链表中每个结点都需要遍历一次，所以时间复杂度与递归相同，为O(m+n)
空间复杂度： 只需要固定大小的额外空间，空间复杂度为O(1)

本文由 李海平 创作，采用知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Jul 30,2019