Solution to LeetCode Merge K Sorted Lists problem.
To merge \(k\) sorted lists, we can use a priority queue that will keep the ordering of the nodes. First, take the first element of all the \(k\) sorted lists, and insert it into the priority queue. The smallest element must be one of these elements. Pop an element off from the priority queue, call it \(m\) and append it to the sorted output. Then, if there exists one, add the successor of \(m\) to the priority queue. Continue this process until all the \(k\) sorted lists are exhausted.
Java code:
public ListNode mergeKLists(ArrayList<ListNode> lists) {
Comparator<ListNode> cmp = new NodeComparator();
PriorityQueue<ListNode> q = new PriorityQueue<ListNode>(lists.size()+1, cmp);
for(int i = 0; i < lists.size(); i++){
if(lists.get(i) != null){
q.add(lists.get(i));
}
}
if(q.isEmpty()) return null;
ListNode root = q.peek();
ListNode tmp = null;
while(!q.isEmpty()){
ListNode top = q.poll();
if(tmp != null) tmp.next = top;
tmp = top;
if(top.next != null) q.add(top.next);
}
return root;
}
class NodeComparator implements Comparator<ListNode>{
public int compare(ListNode n1, ListNode n2){
if(n1.val > n2.val) return 1;
else if(n1.val == n2.val) return 0;
else return -1;
}
}