C++ 392ms beats 99.95% persons


  • 2
    H
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    	if(l1==NULL) return l2;
    	if(l2==NULL) return l1;
    	ListNode *l,*ltemp;
    	if(l1->val <= l2->val)
    	{
    		ltemp=new ListNode(l1->val);
    		l1=l1->next;
    	}
    	else
    	{
    		ltemp=new ListNode(l2->val);
    		l2=l2->next;
    	}
    	l=ltemp;
    	while(l1!=NULL && l2!=NULL)
    	{
    		if(l2==NULL || l1->val <= l2->val)
    		{
    			ltemp->next=new ListNode(l1->val);
    			ltemp=ltemp->next;
    			l1=l1->next;
    		}
    		else if(l1==NULL || l2->val <= l1->val)
    		{
    			ltemp->next=new ListNode(l2->val);
    			ltemp=ltemp->next;
    			l2=l2->next;
    		}
    	}
    	ltemp->next=(l1==NULL)?l2:l1;
    	ltemp=ltemp->next;
    	return l;
    }
    ListNode* mergeKLists(vector<ListNode*>& lists){
    	int size=lists.size();
    	if(size==0)  return NULL;
    	if(size==1)  return lists[0];
    	int i=2,j;
    	while(i/2<size)
    	{
    		for(j=0;j<size;j+=i)
    		{
    			ListNode *p=lists[j];
    			if(j+i/2<size) {
    				p=mergeTwoLists(p,lists[j+i/2]);
    			    lists[j]=p;
    			}
    		}
    		i*=2;
    	}
    	return lists[0];
    }
    

    merge sort!
    WARNING! NOT i=>i+1 but i=>i*2


  • 0
    S

    Nice shot! Just small suggestions:

    1. In your first method, "ltemp=ltemp->next;" in your while-loop could be put out of the if-else statements.
    2. Use a dummy head could make your code more brief.

  • 0
    T

    You could simplify the different types of loops:

    for(int i = 2; i / 2 < size; i *= 2)
    for(int j = 0; j < size; j += i)

  • 0
    T

    +1 for not writing a recursive mergeTwoLists method


  • 0
    T

    Hmm, that 392ms beting everyone doesn't sound right, my Java solution ran in 15ms :) Is this an O(n^2) solution (each item is visited many times)?


  • 0
    H

    how could you?


  • 0
    T
    public ListNode mergeKLists(final ListNode[] lists) {
        if (lists.length == 0) return null;
        PriorityQueue<ListNode> next = new PriorityQueue(lists.length, new Comparator<ListNode>() {
            @Override public int compare(ListNode a, ListNode b) {
                return Integer.compare(a.val, b.val);
            }
        });
        for (int i = 0; i < lists.length; ++i) {
            if (lists[i] != null) next.add(lists[i]);
        }
        
        ListNode fake_head = new ListNode(-1/*irrelevant*/);
        ListNode curr = fake_head;
        while (!next.isEmpty()) {
            curr.next = next.poll();
            curr = curr.next;
            if (curr.next != null) next.add(curr.next);
        }
        return fake_head.next;
    }
    

    and this is a 19.24% solution. Maybe there are different input sets for different languages?


  • 0
    H

    oh my god you're f**king genius! really fast let me have a look!


  • 0
    T

    Hmm, I translated it to C++ and it's 25% (428ms):

    class Solution {
        struct Comparator {
            bool operator()(ListNode* const& a, ListNode* const& b) const {
                return a && b? a->val > b->val : !a; // nulls last
            }
        };
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            if (lists.empty()) return nullptr;
            Comparator min_heap; // re-use given vector to be a minimal priority queue
            make_heap(lists.begin(), lists.end(), min_heap);
            ListNode fake_head(-1/*irrelevant*/);
            ListNode* curr = &fake_head;
            while (!lists.empty()) {
                pop_heap(lists.begin(), lists.end(), min_heap);
        		curr->next = lists.back(); lists.pop_back();
        		if (!curr->next) continue; // this list is finished
                curr = curr->next;
                if (curr->next) { // add next element in selected list
                    lists.push_back(curr->next);
                    push_heap(lists.begin(), lists.end(), min_heap);
                }
            }
            return fake_head.next;
        }
    };
    

    It must be different inputs.


Log in to reply
 

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