[数据结构与算法]【算法100天 | 6】从两个到K个有序链表的合并（LeetCode 21 -＞ 23）

LeetCode 21 合并两个有序链表

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

示例

提示：

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

思路

用迭代的方法； 遍历两个链表（l1、l2），当 l1 和 l2 都不是空链表时，判断 l1 和 l2 哪一个链表的头节点的值更小，将较小值的节点添加到结果里，当一个节点被添加到结果里之后，将对应链表中的节点向后移一位；直到两个链表中有一个链表为空。最后拼接还有剩余节点的链表（l1或l2）

注意：如果两个链表（l1、l2）开始都为空，则直接返回空。

代码

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode dummyHead = new ListNode(-1);
    ListNode cur = dummyHead;
    // 当两个链表都还有节点时，对比节点，找到小的节点
    while(list1 != null && list2 != null) {
        if (list1.val <= list2.val) {
            cur.next = list1;
            list1 = list1.next;
        } else {
            cur.next = list2;
            list2 = list2.next;
        }
        cur = cur.next;
    }
    cur.next = list1 == null ? list2 : list1;
    return dummyHead.next;
}

LeetCode 21 合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例

提示：

• 1k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] 按 升序 排列
• lists[i].length 的总和不超过 10^4

思路

使用优先队列（小顶堆）维护当前每个链表还没有被合并的元素的最前面一个（就每个链表中val最小的节点），因为有k 个链表，所以最多有 k 个满足这样条件的元素（小顶堆的size最大为k），每次在这些元素（小顶堆）里面选取 val 属性最小的元素合并到答案中，直到小顶堆为空。

注意：存在特殊场景[[]]，所以在初始化小顶堆（第一次添加每个链表的头结点到小顶堆）时，要判断节点不为空。

代码

public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null) {
        return null;
    }
    ListNode dummyHead = new ListNode(-1);
    ListNode curr = dummyHead;
    // 小顶堆
    PriorityQueue<ListNode> queue = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
    int length = lists.length;
    for (int i = 0; i < length; i++) {
        if (lists[i] != null) {
            queue.add(lists[i]);
        }
    }
    // 兼容场景：[[]]
    if (queue.isEmpty()) {
        return null;
    }
    while (!queue.isEmpty()) {
        ListNode minNode = queue.poll();
        curr.next = minNode;
        curr = curr.next;
        if (minNode.next != null) {
            queue.offer(minNode.next);
        }
    }
    return dummyHead.next;
}