题目描述

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

输入：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

题目分析

假设链表数量为 k，所有链表节点总数为 n
使用优先队列来寻找最小值
1. 把 k 个头节点放入队列中
2. 从队列中取出最小值，同时把它的next放进队列

队列内最多同时存在 k 个元素，因此每次取最小值，时间复杂度都是 O(log k)
一共需要取值 n 次，时间复杂度是 O(n * log k)

Java

public ListNode mergeKLists(ListNode[] lists) {
    ListNode ans = new ListNode();
    ListNode cur = ans;
    PriorityQueue<ListNode> queue = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.val, o2.val));
    for (ListNode node : lists) {
        if (node != null) {
            queue.offer(node);
        }
    }
    while (!queue.isEmpty()) {
        ListNode node = queue.poll();
        if (node.next != null) {
            queue.offer(node.next);
        }
        cur.next = node;
        cur = cur.next;
    }

    return ans.next;
}

Kotlin

fun mergeKLists(lists: Array<ListNode?>): ListNode? {
    val ans = ListNode(0)
    var cur = ans
    val queue = PriorityQueue<ListNode> { o1, o2 -> Integer.compare(o1.`val`, o2.`val`) }
    for (node in lists) {
        if (node != null) {
            queue.offer(node)
        }
    }
    while (!queue.isEmpty()) {
        val node = queue.poll()
        if (node.next != null) {
            queue.offer(node.next)
        }
        cur.next = node
        cur = cur.next
    }
    return ans.next
}