leetcoe--合并 K 个升序链表(java)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { = val; }
* ListNode(int val, ListNode next) { = val; = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(null == lists || lists.length == 0){
return null;
}
ListNode dump = new ListNode(-1);
ListNode p = dump;
//构建小根堆，
PriorityQueue<ListNode> queue = new PriorityQueue<>((o1,o2)->(o1.val - o2.val));
//先把头节点加入到小根堆中
for(ListNode head : lists){
if(head != null){
queue.add(head);
}
}
while(!queue.isEmpty()){
ListNode cur = queue.poll();
//弹出的第一个 就是最小的头节点。
p.next = cur;
if(cur.next != null){
queue.add(cur.next);
}
//指针不断移动。
p = p.next;
}
return dump.next;
}
}