# Merge k Sorted List

• why does priority queue method need extra space?? the space should be o(1)

• We often implement priority queue by heap, and the heap costs O(k) space. It's such a small space cost generally, but it might be large if we have lots of linked-list to merge.

• What would be the implementation (preferably Python) of the compare one by one?

• @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

• The expected answer got wrong:
When `[[1,2,3],[22,1]]` is input, `[1,1,2,3,22]` should be returned, not `[1,2,3,22,1]`.

• Note [22,1] is not sorted ascending in your input [[1,2,3],[22,1]]

• @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.

• In the merge with divide and conquer, when merging the two lists, why if l2 is bigger do we swap l1 and l2 pointers? My code was accepted without that.

``````    while l1 and l2:
if l1.val <= l2.val:
point.next = l1
l1 = l1.next
else:
point.next = l2
l2 = l2.next
point = point.next``````

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

• why is the space is O(1)? Don't we add up the tmp space for every recursive call in the process of merge???

• @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/why-is-mergesort-space-complexity-ologn-with-linked-lists

• @dragonfly1912 Yep, I think it is O(logk). Thank you for your reference!

• 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 o1-o2;
}

});
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{
while(lists[i].next!=null){
lists[i]=lists[i].next;
}
}catch (NullPointerException e){}

}
Collections.sort(aList);

ListNode resultList=new ListNode(0);
for(int j=0;j<aList.size();j++){
resultList.next = new ListNode(aList.get(j));
resultList = resultList.next;
}