2018-11-25 22:58:52
问题描述：
问题求解：
本题可以使用优先队列高效的进行求解，整体的时间复杂度为O(nlogk)。
public ListNode mergeKLists(ListNode[] lists) {
ListNode dummy = new ListNode(-1);
ListNode prev = dummy;
int k = lists.length;
PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {
@Override
public int compare(ListNode o1, ListNode o2) {
return o1.val - o2.val;
}
});
for (int i = 0; i < k; i++) if (lists[i] != null) pq.add(lists[i]);
while (!pq.isEmpty()) {
ListNode curNode = pq.poll();
prev.next = curNode;
prev = prev.next;
if (curNode.next != null) pq.add(curNode.next);
}
return dummy.next;
}