面试热题（合并K个升序链表）

给定一个链表数组，每个链表都已经按升序排列。

请将所有链表合并到一个升序链表中，返回合并后的链表。

输入：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个升序列表已经合并完成

 

public ListNode mergeKLists(ListNode[] lists) {if(lists==null||lists.length==0){return null;}//自定义比较器PriorityQueue<ListNode> queue=new PriorityQueue<>(new Comparator<ListNode>() {@Overridepublic int compare(ListNode o1, ListNode o2) {return o1.val-o2.val;}});//将K个节点的头结点入队for(ListNode node:lists){if(node!=null){queue.offer(node);}}//创建一个虚拟头结点ListNode dummyNode=new ListNode(-1);ListNode curNode=dummyNode;while(!queue.isEmpty()){ListNode cur=queue.poll();curNode.next=cur;//更新curNodecurNode=curNode.next;//如果当前节点的next不为空，则让下一个节点进行入队if(cur.next!=null){queue.offer(cur.next);}}return dummyNode.next;}