-
Notifications
You must be signed in to change notification settings - Fork 0
Merge k sorted list
Tim_Gao edited this page Sep 17, 2016
·
1 revision
- mistake made: how to write a class that can be fed to PriorityQueue
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class QueueNode implements Comparable<QueueNode> {
public ListNode ln;
public QueueNode(ListNode n){
ln = n;
}
public int compareTo(QueueNode other){
return this.ln.val - other.ln.val;
}
}
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
ListNode head = null, prev = null;
if (lists.length == 0){
return head;
}
PriorityQueue<QueueNode> heap = new PriorityQueue<>();
for (ListNode ln : lists){
if (ln!=null )
heap.offer(new QueueNode(ln));
}
while (!heap.isEmpty()){
QueueNode qn = heap.poll();
ListNode crt = qn.ln;
if (qn.ln.next != null){
qn.ln = qn.ln.next;
heap.offer(qn);
}
crt.next = null;
if (head == null){
head = crt;
}
if (prev!=null){
prev.next = crt;
}
prev = crt;
}
return head;
}
}