Clean and concise solution in c++ using merge2lists . Time : O(n*log(k)) Space: O(1)


  • 2
    S
    class Solution {
    public:
        ListNode* merge2Lists(ListNode* head1 , ListNode*head2){
            ListNode* d = new ListNode(0);
            ListNode* e = d;
            while(head1 && head2){
                if(head1 -> val <= head2->val ){
                    e = e->next = head1;
                    head1= head1->next;
                }
                else if(head2 -> val < head1->val ){
                    e = e->next = head2;
                    head2= head2->next;
                }
            }
            if(!head1) e->next =head2;
            if(!head2) e->next = head1;
            ListNode * ret =d->next;
            delete d;
            return ret;
        }
        
        ListNode* mergeKLists(vector<ListNode*>& a) {
            int n = a.size();
            if(n==0) return NULL;
            while(n>1){
                if(n%2 == 1) {a[n]=NULL;n++;}               // to make n even 
                for(int i=0 ; i < (n)/2 ; i++ ){
                    a[i] = merge2Lists( a[i] , a[i+ (n/2)]);
                }
                n= n/2;
            }
            return a[0];
        }
    };

  • 0
    H

    why the "a[n]=NULL" don't need to "resize(n+1)" ? i think you should add this.


Log in to reply
 

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