【24.合并K个升序链表】

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

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

示例 1：

输入：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
示例 2：

输入：lists = []
输出：[]
示例 3：

输入：lists = [[]]
输出：[]
 

提示：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*//**容量为K的小顶堆，用来存放链表的头节点，取出队头的结点挂到链表中让出队的那个节点的下一个结点入队直至堆为空*/
class Solution {public ListNode mergeKLists(ListNode[] lists) {int len=lists.length;if(len == 0) return null;//如果lists里边没有元素，直接返回ListNode res=new ListNode(0);ListNode cur=res;//实现一个自定义排序：在内部new这个接口Comparator，并重写里面的Compare方法PriorityQueue<ListNode> pq=new PriorityQueue<ListNode>(new Comparator<ListNode>(){@Overridepublic int compare(ListNode l1,ListNode l2){   return l1.val-l2.val;}});for(ListNode list:lists){if(list == null){continue;//遇到空的链表，跳过去}pq.add(list);//优先队列列pq存放链表的头结点}while(!pq.isEmpty()){//只要堆不空，继续循环ListNode listNode=pq.poll();//将队头节点取出cur.next=listNode;//将队头结点挂到链表中cur=cur.next;//链表指针往后挪一位if(listNode.next != null){listNode=listNode.next;pq.add(listNode);//队头结点所在的链表的下一个节点入队}}return res.next;}
}