链表合并

统计信息：字数 3841 阅读8分钟

No.1 合并两个有序链表

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

示例:

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

来源: LeetCode第21题

递归解法

递归解法更容易理解，我们先用递归来做一下:

    /**
     * @param {ListNode} l1
     * @param {ListNode} l2
     * @return {ListNode}
     */
    var mergeTwoLists = function(l1, l2) {
        const merge = (l1, l2) => {
            if(l1 == null) return l2;
            if(l2 == null) return l1;
            if(l1.val > l2.val) {
                l2.next = merge(l1, l2.next);
                return l2;
            }else {
                l1.next = merge(l1.next, l2);
                return l1;
            }
        }
        return merge(l1, l2);
    };

循环解法

    var mergeTwoLists = function(l1, l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        let p = dummyHead = new ListNode();
        let p1 = l1, p2 = l2;
        while(p1 && p2) {
            if(p1.val > p2.val) {
                p.next = p2;
                p = p.next;
                p2 = p2.next;
            }else {
                p.next = p1;
                p = p.next;
                p1 = p1.next;
            }
        }
        // 循环完成后务必检查剩下的部分
        if(p1) p.next = p1;
        else p.next = p2;
        return dummyHead.next;
    };

No.2 合并 K 个有序链表

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

来源: LeetCode第23题

自上而下(递归)实现

    /**
     * @param {ListNode[]} lists
     * @return {ListNode}
     */
    var mergeKLists = function(lists) {
        // 上面已经实现
        var mergeTwoLists = function(l1, l2) {/*上面已经实现*/};
        const _mergeLists = (lists, start, end) => {
            if(end - start < 0) return null;
            if(end - start == 0)return lists[end];
            let mid = Math.floor(start + (end - start) / 2);
            return mergeTwoList(_mergeLists(lists, start, mid), _mergeLists(lists, mid + 1, end));
        }
        return _mergeLists(lists, 0, lists.length - 1);
    };

自下而上实现

在这里需要提醒大家的是，在自下而上的实现方式中，我为每一个链表绑定了一个虚拟头指针(dummyHead)，为什么这么做？

这是为了方便链表的合并，比如 l1 和 l2 合并之后，合并后链表的头指针就直接是 l1 的 dummyHead.next 值，等于说两个链表都合并到了 l1 当中，方便了后续的合并操作。

var mergeKLists = function(lists) {
    var mergeTwoLists = function(l1, l2) {/*上面已经实现*/};
    // 边界情况
    if(!lists || !lists.length) return null;
    // 虚拟头指针集合
    let dummyHeads = [];
    // 初始化虚拟头指针
    for(let i = 0; i < lists.length; i++) {
        let node = new ListNode();
        node.next = lists[i];
        dummyHeads[i] = node;
    }
    // 自底向上进行merge
    for(let size = 1; size < lists.length; size += size){
        for(let i = 0; i + size < lists.length;i += 2 * size) {
            dummyHeads[i].next = mergeTwoLists(dummyHeads[i].next, dummyHeads[i + size].next);
        }
    }
    return dummyHeads[0].next;
};

多个链表的合并到这里就实现完成了，在这里顺便告诉你这种归并的方式同时也是对链表进行归并排序的核心代码。希望你能好好体会自上而下和自下而上两种不同的实现细节，相信对你的编程内功是一个不错的提升。

---

Last update: November 9, 2024