public class Solution_104 {
/**
* @param lists: a list of ListNode
* @return: The head of one sorted list.
*/
class ListNodeComparator implements Comparator<ListNode>{
@Override
public int compare(ListNode l1,ListNode l2){
return l1.val-l2.val;
}
}
public ListNode mergeKLists(List<ListNode> lists){
if(lists==null || lists.size()==0){
return null;
}
Comparator<ListNode> comparator=new ListNodeComparator();
PriorityQueue<ListNode> heap=new PriorityQueue<ListNode>(lists.size(),comparator);
//get the first element of each list
for(int i=0;i<lists.size();i++){
if(lists.get(i)!=null){
heap.add(lists.get(i));
}
}
ListNode dummy=new ListNode(0);
ListNode temp=dummy;
while(!heap.isEmpty()){
ListNode currentMin=heap.poll();
temp.next=currentMin;
if(currentMin.next!=null){
heap.add(currentMin.next);
}
//equal to temp=temp.next;
temp=currentMin;
}
return dummy.next;
}
}
Version 2:
合并 k 个有序链表的逻辑类似合并两个有序链表，难点在于，如何快速得到 k 个节点中的最小节点，接到结果链表上？
ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) return null;
// 虚拟头结点
ListNode dummy = new ListNode(-1);
ListNode p = dummy;
// 优先级队列，最小堆
PriorityQueue<ListNode> pq = new PriorityQueue<>(
lists.length, (a, b)->(a.val - b.val));
// 将 k 个链表的头结点加入最小堆
for (ListNode head : lists) {
if (head != null)
pq.add(head);
}
while (!pq.isEmpty()) {
// 获取最小节点，接到结果链表中
ListNode node = pq.poll();
p.next = node;
if (node.next != null) {
pq.add(node.next);
}
// p 指针不断前进
p = p.next;
}
return dummy.next;
}