Got TEL using merge sort, which is O(nlogn), any one have better solution


  • 1
    B
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode *mergeKLists(vector<ListNode *> &lists) {
            
            int n = lists.size();
            int groupNum = n/2;
            int i;
            ListNode* result;
            ListNode* head;
            ListNode* index1;
            ListNode* index2;
            ListNode* previous;
            ListNode* tempIndex;
            
            vector<ListNode*> tempList;
            vector<ListNode*> sorted;
            vector<ListNode*> temp;
            sorted = lists;
            
            if(lists.size()==0) return NULL;
            if(lists.size()==1) return lists[0];
            
            while(groupNum>=1)
            {
                for(i=0;i<groupNum;i++)
                {
                    //merge linked list
                    index1 = sorted[2*i];
                    index2 = sorted[2*i+1];
                    
                    head = index1;
                    
                    if(!index1 && !index2)
                    {
                        continue;
                    }    
                    else if(index1 && !index2)
                    {
                        tempList.push_back(index1); 
                        continue;
                    }
                    else if(!index1 && index2)
                    {
                        tempList.push_back(index2);
                        continue;
                    }
                    
                    previous = NULL;
                    
                    while(index1 && index2)
                    {
                        if(index1->val > index2->val)
                        {
                            if(previous)
                            {
                                previous->next = index2;
                            }
                            else
                            {
                                head = index2;
                            }
                            
                            tempIndex = index2->next;
                            index2->next = index1;
                            index2 = tempIndex;
                            
                            previous = index2;
                        }
                        else
                        {
                            previous = index1;
                            index1= index1->next;
                        }
                    }
                    
                    if(index2)
                    {
                        previous->next = index2;    
                    }
                    
                    //add merged list into vector
                    tempList.push_back(head);
                }
                
                //change groupNum
                if(sorted.size()-2*groupNum >0) tempList.push_back(sorted[sorted.size()-1]);
                
                temp = sorted;
                sorted = tempList;
                tempList = temp;
                tempList.clear();
                
                groupNum = sorted.size()/2;
            }
            
            result = sorted[0];
            return result;
        }
    };

  • 0
    S

    Thanks for your post. I just updated your post with correct code format, hope you will pay attention next time.


Log in to reply
 

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