[c++] Runtime 32msec


  • 0
    S
    class Solution {
    public:
    
        ListNode *mergeTwoLists(ListNode *first, ListNode *second)
        {
            if(first==NULL)
                return second;
            else if(second==NULL)
                return first;
                
            ListNode *ansHead,*ansCur;
            ansHead=NULL;
            while(first && second)
            {
                if(first->val<=second->val)
                {
                    if(ansHead==NULL)
                    {
                        ansHead=first;
                        ansCur=first;
                    }
                    else
                    {
                        ansCur->next=first;
                        ansCur=first;
                    }
                    first=first->next;
                }
                else
                {
                    if(ansHead==NULL)
                    {
                        ansHead=second;
                        ansCur=second;
                    }
                    else
                    {
                        ansCur->next=second;
                        ansCur=second;
                    }
                    second=second->next;
                }
            }//end while
            if(first)
            {
                ansCur->next=first;
            }
            else
            {
                ansCur->next=second;
            }
            return ansHead;
        }
        
        ListNode *BinaryMergeLists(vector<ListNode*>& lists, int start, int end)
        {
            if(start>end)
            {
                return NULL;
            }
            //if only one list
            if(start==end)
            {
                return lists[start];
            }
            //if two lists
            if(start+1==end)
            {
                return mergeTwoLists(lists[start],lists[end]);
            }
            
            //else merge each two halves seperately
            int mid=(start+end)/2;
            
        
            return mergeTwoLists(BinaryMergeLists(lists,start,mid),BinaryMergeLists(lists,mid+1,end));
        }
        
        ListNode* mergeKLists(vector<ListNode*>& lists) 
        {
            //handle vector of size 1
            if(lists.size()==1)
                return lists[0];
            ListNode *head=NULL;
            head = BinaryMergeLists(lists,0,lists.size()-1);
            return head;
        }
    };

Log in to reply
 

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