Merge K sorted lists into one big sorted list in ascending order.
Assumptions
- ListOfLists is not null, and none of the lists is null.
public ListNode merge(List<ListNode> listOfLists) {
PriorityQueue<ListNode> pq = new PriorityQueue(1, new Comparator<ListNode>() {
public int compare(ListNode a, ListNode b) {
return a.value - b.value;
}
});
for (ListNode head : listOfLists) {
if (head == null) {
continue;
}
pq.offer(head);
}
ListNode prev = null, head = null;
boolean isFirst = true;
while (!pq.isEmpty()) {
ListNode cur = pq.poll();
if (isFirst) {
prev = cur;
head = cur;
isFirst = false;
} else {
prev.next = cur;
prev = cur;
}
if (cur.next != null) {
pq.offer(cur.next);
}
}
return head;
}