题目描述

题目链接

https://leetcode.cn/problems/merge-k-sorted-lists/

思路

在解决「合并 K 个排序链表」这个问题前，我们先来看一个更简单的问题：如何合并两个有序链表？

假设链表和的长度都是，如何在的时间代价以及的空间代价完成合并？ 这个问题在面试中常常出现，为了达到空间代价是，我们的宗旨是「原地调整链表元素的指针完成合并」。以下是合并的步骤和注意事项。

• 首先我们需要一个哨兵节点来保存合并之后链表的头部，这是为了方便代码的书写，在整个链表合并完之后，返回它的下一位置即可。
• 我们需要一个指针来记录下一个插入位置的前一个位置，以及两个指针和来记录和未合并部分的第一位。注意，不是下一个插入的位置，和所指向的元素处于「待合并」的状态，也就是说它们还没有合并入最终的链表。
• 当和都不为空时，取较小的合并；如果为空，则把整个以及后面的元素全部合并；为空时同理。

下图展示了和两个链表迭代合并的过程：

具体代码实现如下：

public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
    ListNode preHead = new ListNode(-1);
    ListNode prev = preHead;
    // 合并有序链表
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            prev.next = l1;
            l1 = l1.next;
        } else {
            prev.next = l2;
            l2 = l2.next;
        }
        prev = prev.next;
    }
    // 合并剩余的有序链表
    prev.next = l1 == null ? l2 : l1;
    return preHead.next;
}

1. 顺序合并

我们可以想到一种最朴素的方法：用一个变量来维护以及合并的链表，第次循环把第个链表和合并，答案保存到中

public ListNode mergeKLists(ListNode[] lists) {
    ListNode ans = null;
    for (ListNode list : lists) {
        // 逐一合并
        ans = mergeTwoLists(ans, list);
    }
    return ans;
}

• 时间复杂度：假设每个链表的最长长度是。在第一次合并后，的长度为；第二次合并后，的长度为，第次合并后，的长度为。第次合并的时间代价是，那么总的时间代价为，故渐进时间复杂度为。

• 空间复杂度：没有用到与和规模相关的辅助空间，故渐进空间复杂度为。

  2. 分治合并

  考虑优化方法一，采用分治的方法进行合并。

• 将个链表配对并将同一对中的链表合并；

• 第一轮合并后，个链表被合并成了个链表，平均长度为，然后是、个链表等等；
• 重复这一过程，直到我们得到了最终的有序链表。

具体代码实现如下：

public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) {
        return null;
    }
    return merge(lists, 0, lists.length - 1);
}

private ListNode merge(ListNode[] lists, int start, int end) {
    if (start > end) {
        return null;
    }
    if (start == end) {
        return lists[start];
    }
    // 通过归并思想进行有序链表的两两合并
    int middle = start + (end - start) / 2;
    return mergeTwoLists(merge(lists, start, middle), merge(lists, middle + 1, end));
}

• 时间复杂度：考虑递归「向上回升」的过程——第一轮合并组链表，每一组的时间代价是；第二轮合并组链表，每一组的时间代价是……所以总的时间代价是，故渐进时间复杂度为。
• 空间复杂度：递归会使用到空间代价的栈空间。

  3. 使用优先队列合并

  这个方法和前两种方法的思路有所不同，我们需要维护当前每个链表没有被合并的元素的最前面一个，个链表就最多有个满足这样条件的元素，每次在这些元素里面选取属性最小的元素合并到答案中。通过局部最优来达到全局最优。

这里我们举一个生活中的例子来理解这个思路：

假设你是一名体育老师，有个班的学生，他们已经按照身高从矮到高排好成了列纵队，现在要把这个班的学生也按照身高从矮到高排成列纵队。我们可以这么做：

1. 让个班的学生按列站在你的面前，这时你能看到站在队首的学生的全身；
2. 每一次队首的名同学，请最矮的同学出列到“队伍4”（即我们最终认为排好序的队列），出列的这一列的后面的所有同学都向前走一步；
3. 重复第 2 步，直到个班的同学全部出列完毕。

在具体如何选取最小元素的时候，我们可以用「优先队列」来优化这个过程。

具体代码实现如下：

public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) {
        return null;
    }
    // 添加链表节点到优先队列中
    PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));
    for (ListNode list : lists) {
        if (list != null) {
            priorityQueue.add(list);
        }
    }

    ListNode dummyNode = new ListNode(-1);
    ListNode curNode = dummyNode;
    while (!priorityQueue.isEmpty()) {
        ListNode node = priorityQueue.poll();
        // 当前节点的 next 指针指向出队元素
        curNode.next = node;
        // 当前指针向前移动一个元素，指向了刚刚出队的那个元素
        curNode = curNode.next;
        // 将链表的下一个节点添加到优先队列中
        if (curNode.next != null) {
            priorityQueue.add(curNode.next);
        }
    }
    return dummyNode.next;
}

• 时间复杂度：考虑优先队列中的元素不超过个，那么插入和删除的时间代价为，这里最多有个点，对于每个点都被插入删除各一次，故总的时间代价即渐进时间复杂度为。
• 空间复杂度：这里用了优先队列，优先队列中的元素不超过个，故渐进空间复杂度为。