23. Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example
Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->
题意：给出了 k 个已经排好序的 linkedlist， 把他们合并成一个有序的 linkedlist.
这个比较直接。用 pq 存各个链表的头部，然后取出最小的， 然后查看是否有 next， 有的话 push 到队列里面。 这样的话我们对 heap 总共进行 n 次操作（总元素个数）， heap的 size 为 lists 的个数 k。 那么复杂度就是 nlogk
代码
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> pq = new PriorityQueue<>((a,b) -> a.val - b.val);
ListNode dummyNode = new ListNode(-1);
for(int i = 0; i < lists.length; i++) {
if(lists[i] != null)pq.offer(lists[i]);
}
ListNode cur = null, p = dummyNode;
while(!pq.isEmpty()) {
cur = pq.poll();
if(cur.next != null) pq.offer(cur.next);
p.next = cur;
p = p.next;
}
return dummyNode.next;
}
}