Merge k Sorted List


  • 0

    Click here to see the full article post


  • 0
    S

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


  • 0

    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.


  • 0
    N

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


  • 0

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


  • -1
    P

    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


  • -1
    T

    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].


  • 0
    F

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


  • 0
    P

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


  • 0
    P

    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

  • 0
    Q

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


  • 1
    D

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


  • 0
    D

    @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


  • 0
    D

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


  • 0
    W

    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;
    }


  • 0
    W

    //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;

  • 0
    C
        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?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.