Merge k Sorted List


@NickPuljic The Priority Queue method actually do the same thing as comparing one by one: select the smallest node among k heads of list. If you like, you can just compare the k nodes one by one which costs O(k).

class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length == 0)
return null;
ListNode result = null;
ListNode x = null;
int min = Integer.MAX_VALUE;
int minIndex = 0;
while(true) {
boolean zerofound = true;
for(int i = 0; i < lists.length; i++) {
if(lists[i] == null) continue;
zerofound = false;
if(lists[i].val < min) {
min = lists[i].val;
minIndex = i;
}
}if(zerofound == true) break; if(result == null) { result = lists[minIndex]; x = result; } else { x.next = lists[minIndex]; x = x.next; } lists[minIndex] = lists[minIndex].next; min = Integer.MAX_VALUE; } return result; }
}
Can anybody explain what is wrong with this solution this is compare one by one. This gives runtime error for the 130th test case which is the last test case

@priyekant I had the same issue with my one by one solution. I think one by one solution is just too slow for the test time cutoff.

@Hermann0 It does not do the same thing. Priority queue gets the smallest with O(lgK), while compare one by one costs O(K)

@danielwx I have the same question. I think it should be O(log k) for recursive stack, just like merge sort. Read more here: https://stackoverflow.com/questions/24171242/whyismergesortspacecomplexityolognwithlinkedlists


public ListNode mergeKLists(ListNode[] lists) {
//this is Approach #2 ,it is ok in my computer,
//but it is Time Limit Exceeded,why?
int k = lists.length;
ListNode newNode =new ListNode(0);
ListNode first =newNode;//当前指针
int index =0;
boolean flag =true;
if(k==0) return null;
while(flag) {//Traverse all nodes and stop
int nullNum =0;//the number of Null node
int temp =Integer.MAX_VALUE;
for(int i = 0;i<k;i++) {//遍历k格链表，获取当前节点
if(lists[i]==null) {
nullNum++;
}else if(lists[i].val<=temp) {
temp =lists[i].val;
index =i;
}
}
first.next =lists[index];
first = first.next;
if(lists[index]!=null) {
lists[index] =lists[index].next;
}
flag =nullNum==k?false:true;//Traverse all nodes
}
return newNode.next;
}

//The answer is accepted！But,I do not know how to calculate the time complexity.It may be O(Nlogk) or others.The same as approach#3?
int k =lists.length;
ListNode dummy =new ListNode(0);
ListNode first =dummy;
Map<Integer,Integer> map =new TreeMap<>(
new Comparator<Integer>() {@Override public int compare(Integer o1, Integer o2) { return o1o2; } }); for(int i =0;i<k;i++) { ListNode temp =lists[i]; while(temp!=null) { if(!map.containsKey(temp.val)) { map.put(temp.val, 1); }else { map.put(temp.val, map.get(temp.val)+1); } temp = temp.next; } } for(Integer val:map.keySet()) { for(int i=0;i<map.get(val);i++) { first.next =new ListNode(val); first =first.next; } } return dummy.next;

while l1 and l2: if l1.val <= l2.val: point.next = l1 l1 = l1.next else: point.next = l2 l2 = l1 l1 = point.next.next point = point.next
For the else section why is the l2 and l1 switched? Isn't this unnecessary? Not to mention... Doesn't this mess up "point.next = l2" and make it essentially "point.next = l1" since "l2 = l1" in the following line?

Simple Java implementation,time complexityO(NlogN), Space complexityO(N):
public ListNode mergeKLists(ListNode[] lists) {
ArrayList<Integer> aList = new ArrayList<Integer>(); for(int i=0;i<lists.length;i++){ try{ aList.add(lists[i].val); while(lists[i].next!=null){ aList.add(lists[i].next.val); lists[i]=lists[i].next; } }catch (NullPointerException e){} } Collections.sort(aList); ListNode resultList=new ListNode(0); ListNode head = resultList; for(int j=0;j<aList.size();j++){ resultList.next = new ListNode(aList.get(j)); resultList = resultList.next; } return head.next; }

@danielwx I think it is O(1) because each call to merge2Lists() returned immediately after pushing onto the stack. If you write in a topdown fashion, it is O(log(k)) due to tall stack.