Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null || lists.length == 0) //pay attention to null
return null; ListNode head = null;
ListNode cur = head; //cur.next point to the node to give value
PriorityQueue<ListNode> minHeap = new PriorityQueue<>(lists.length,
new Comparator<ListNode>(){ //小顶堆，默认容量11，这里改为列表长度
@Override
public int compare(ListNode n1, ListNode n2){
return n1.val - n2.val;
}
}); for(ListNode n: lists){
if(n!=null) minHeap.add(n); //pay attention to null
} while(minHeap.size()>0){
//pop
if(head==null){
head = minHeap.poll();
cur = head;
}
else{
cur.next = minHeap.poll();
cur = cur.next;
} //push
if(cur.next != null){
minHeap.add(cur.next);
}
}
return head;
}
}
PriorityQueue是通过小顶堆实现的，如果要使用大顶堆，那么需要自定义Comparator函数。
List问题特别注意：需要额外讨论null的情况，比如本题中，需要保证PriorityQueue不能加入null元素。