【遍历, 优先队列】合并K个升序链表

题目

23. 合并K个升序链表

---

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

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

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

• k == 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

解题

方法一：遍历

思路

和 【链表, 双指针】合并两个有序链表 思路差不多，只不过两个链表换成了 K 个链表。

代码

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int len = lists.length;
        ListNode dummy = new ListNode(), prev = dummy;
        while (true) {
            int minIdx = 0, minVal = Integer.MAX_VALUE;
            boolean hasMin = false;
            for (int i = 0; i < len; i++) {
                ListNode curr = lists[i];
                if (curr == null) continue;
                if (curr.val < minVal) {
                    hasMin = true;
                    minIdx = i;
                    minVal = curr.val;
                }
            }
            if (!hasMin) break;
            prev.next = new ListNode(minVal);
            prev = prev.next;
            lists[minIdx] = lists[minIdx].next;
        }
        return dummy.next;
    }
}

方法二：优先队列(小根堆)

思路

维护一个存储节点优先队列，按照节点值的大小升序。把数组中所有不为空的节点入队。创建一个哨兵节点(dummy)与一个遍历节点(prev)用于在其后面连接几点，当队列不为空时每次取一个队头元素(值最小)出来接在遍历节点的后面，遍历节点向后推，如果该队头节点的后继节点不为空时，把该节点入队。最后返回哨兵节点的后继节点即可。

代码

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        Queue<ListNode> minHeap = new PriorityQueue<ListNode>((a, b) -> a.val - b.val);
        for (ListNode list : lists) {
            if (list != null) minHeap.offer(list);
        }
        ListNode dummy = new ListNode(), curr = dummy;
        while (!minHeap.isEmpty()) {
            ListNode minNode = minHeap.poll();
            curr.next = minNode;
            curr = curr.next;
            if (minNode.next != null) minHeap.offer(minNode.next);
        }
        return dummy.next;
    }
}

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> min_heap(cmp);
        for (auto list : lists) {
            if (list) min_heap.push(list);
        }
        ListNode* dummy = new ListNode(), * curr = dummy;
        while (!min_heap.empty()) {
            ListNode* min_node = min_heap.top();
            min_heap.pop();
            curr->next = min_node;
            curr = curr->next;
            if (min_node->next) min_heap.push(min_node->next);
        }
        return dummy->next;
    }
};