Add left 1 check and decrease list size still timeout


  • 0
    D

    already check is the last non-null in 'lists' and decrease listsSize when any list seek to end, but it still timeout, any way beyond O(M*N) ?

    struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
            struct ListNode* res = NULL;
            struct ListNode* min = NULL;
            struct ListNode* pre = NULL;
            int min_index = -1;
            int left_count = 0;
            if(listsSize == 0)
                return NULL;
            if(listsSize == 1)
                return lists[0];
            while(true)
            {
                min = NULL;
                min_index = -1;
                left_count = 0;
                for(int i = 0; i < listsSize; ++i)
                {
                    if(lists[i] != NULL)
                    {
                        left_count++;
                        if(min == NULL || lists[i]->val < min->val)
                        {
                            min = lists[i];
                            min_index = i;    
                        }
                    }
                }
                if(min == NULL)
                    return res;
                else
                {
                    if(res == NULL)
                    {
                        res = min;
                        pre = min;
                    }
                    else
                        pre->next = min;
                }
                if(left_count == 1)
                    return res;
                lists[min_index] = lists[min_index]->next;
                if(lists[min_index] == NULL)
                    lists[min_index] = lists[--listsSize];
            }
            return res;
        }

  • 0

Log in to reply
 

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