Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
public ListNode mergeKLists(ArrayList<ListNode> lists) {
// Start typing your Java solution below
// DO NOT write main() function
ListNode fakeHead = new ListNode(-1);
ListNode runner = fakeHead;
int nonTraversed = 0;
//count the number of not-null ListNode
for(ListNode curr:lists){
if(curr!=null){
nonTraversed++;
}
}
while(nonTraversed>0){
int min = Integer.MAX_VALUE;
int minIndex = -1;
for(int i=0;i<lists.size();i++){
ListNode curr = lists.get(i);
if(curr!=null){
if(curr.val<min){
minIndex = i;
min = curr.val;
}
}
}
runner.next = lists.get(minIndex);
runner = runner.next;
lists.set(minIndex, lists.get(minIndex).next);
if(lists.get(minIndex)==null){
nonTraversed--;
}
}
return fakeHead.next;
}
O(N*k) k is the size of lists and N is the total number of elements in all the inputs lists
We can improve our solution by using Heap which can have O(Nlogk) runtime complexity.
