给你一个链表数组,每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中,返回合并后的链表。
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
/**
用优先队列(给他一个排序器),先把每一个头结点放进去
开一个带亚节点的作为结果链表
然后遍历队列, 每次拿出最小的来,删掉,尾插入结果中 然后添加当前头结点的链表所有元素
以此类推,吧剩余的所有头结点的链表都加进去,然后并删除
*/
ListNode res=new ListNode(-1);
ListNode head=res; //操作这个head
//开一个排序器 小跟堆
PriorityQueue<ListNode> pq=new PriorityQueue<ListNode>((o1,o2)->o1.val-o2.val);
for(ListNode node:lists){
if(node!=null)
pq.add(node); //吧所有头结点加入
}
while(!pq.isEmpty()){
ListNode min=pq.poll();//把最小的拿出
head.next=min;//尾插
head=head.next;
if(min.next!=null){
//遍历当前头节点
pq.offer(min.next);
}
}
return res.next;
}
}