Time limit in my c++ code,help


  • 0
    A

    my solution is compare the k lists first node,find the nodes,then make the nodes point to next,and update the pointer in vector.after all the pointer in vector are NULL,then compare is over.

    Time limit test case is all the vector list are one node and the vector size is very big.

     class Solution {
    public:
        ListNode *mergeKLists(vector<ListNode *> &lists) {
            ListNode head(0);
            ListNode *p = &head;
            ListNode *temp = NULL;
            int nsize = lists.size();
            int nfind =0;
            while(1)
            {
                for(int i =0;i<nsize;i++)
                {   
                    if(NULL != lists[i] &&  NULL == temp )
                    {
                        temp = lists[i];
                        nfind = i;
                    }
                    else if(NULL != lists[i] && lists[i]->val < temp->val)
                    {
                        temp = lists[i];
                        nfind = i;
                    }
                }
                
                if(NULL == temp)
                {
                    break;
                }
                p->next = temp;
                p = temp;
                lists[nfind]= temp =temp->next;
                temp = NULL;
            }
            return head.next;
        }
    };

  • 0

    this is a method, but not good.

    think about this. the total number of the lists's nodes is N. and the size of the lists is size.

    so your method's time complexity is Nsize*.

    try my method:

    ListNode *mergeKLists(vector<ListNode *> &lists) 
    {
    	int size = lists.size();
    	if (0 == size)	return NULL;
    
    	for (int i = 1; i < size; i = i + i)
    		for (int j = i; j < size; j += 2*i)
                        //merge two lists to one
    			lists[j - i] = mergeTwoLists(lists[j - i], lists[j]);
    
    	return lists[0];
    }

Log in to reply
 

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