Merge k Sorted Lists
给k个sorted list, 然后merge. 用一个heap存每个list的当前元素. 然后组一个list.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length == 0 || lists == null)
return null;
PriorityQueue<ListNode> q = new PriorityQueue<ListNode>(lists.length, new Comparator<ListNode>(){
public int compare(ListNode a, ListNode b) {
if(a.val > b.val)
return 1;
else if(a.val < b.val)
return -1;
else
return 0;
}
});
for(int i = 0 ; i < lists.length; i++) {
if(lists[i] != null)
q.add(lists[i]);
}
ListNode head = new ListNode(0);
ListNode p = head;
while(!q.isEmpty()){
ListNode node = q.poll();
p.next = node;
if(node.next != null)
q.add(node.next);
p = p.next;
}
return head.next;
}
}