# Simple JAVA Nlog(K) solution with explanation

• Here is my simple nlog(k) solution where n refers the total number of nodes we have.

The idea is that we maintain a min-heap with capacity of k elements. Since all lists are sorted, the current minimum node must be one of the top-most elements among those lists, so here we can offer all k top-most nodes into min-heap where extracting the min value is log(k) time. But each time we also have to insert a new node and the node should come from the very list we just extract a min node from! This is how we make sure the next min node is inside our heap but not somewhere in a list. I build a hash map "lookUpTable" to accomplish this step, the key is node and value is its corresponding index of input lists array, after extracting a node, we can easily trace back to the very list the node comes from.

Because the size of min-heap is always bounded by k, and we at most extract n times, the running time would be O(nlog(k)) therefore.

``````public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
int len = lists.length;
if(len == 0) return null;

HashMap<ListNode, Integer> lookUpTable = new HashMap<>();
PriorityQueue<ListNode> que = new PriorityQueue<>((a,b)->a.val - b.val);
for(int i=0; i<len; i++){
ListNode cur = lists[i];
if(cur == null) continue;
que.offer(cur);
lookUpTable.put(cur, i);
}

ListNode head = null, cur = null, nextInput = null, pre = null;
while(!que.isEmpty()){
cur = que.poll();
int idx = lookUpTable.get(cur);
lookUpTable.remove(cur);
nextInput = lists[idx].next;
lists[idx] = nextInput;
if(nextInput != null){
que.offer(nextInput);
lookUpTable.put(nextInput, idx);
}