Solution by <644367822>


  • 0
    6

    Approach #1 Brute Force [Accepted]

    Algorithm

    This is a simple solution , we merge each two lists from 0 to k ( lists size ) .
    We can refer to 21. Merge Two Sorted Lists

    c++

    class Solution {
    public:
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
            ListNode* head = new ListNode(0) ;
            ListNode* p = head ;
            while( l1 != NULL && l2 != NULL ) {
                if( l1->val <= l2->val ) {
                    p->next = l1 ;
                    p = p->next ;
                    l1 = l1->next ;
                }
                else {
                    p->next = l2 ;
                    p = p->next ;
                    l2 = l2->next ;
                }
            }
            if( l1 != NULL ) {
                p->next = l1 ;
            }
            else if( l2 != NULL ) {
                p->next = l2 ;
            }
            return head->next;
        }
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            if( lists.size() == 0 ) {
                return NULL;
            }
            ListNode *ans = lists [0] ;
            for( int i = 1 ;i < lists.size() ; i ++ ) {
                ans = mergeTwoLists( lists[i] , ans ) ;
            }
            return ans ;
        }
    };
    

    Complexity Analysis

    • Time complexity : $O(N^2*M)$. Here M is the average size of lists .
    • Space complexity : $O(1)$.

    Approach #2 Heap [Accepted]

    Algorithm

    We can use priority_queue to save the element of the lists . Then reconstruct the list with heap .

    c++

    class Solution {
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            priority_queue <int , vector<int> , greater<int> > qlist ;
            for( int i = 0 ; i < lists.size() ; i ++ ) {
                while( lists[i] != NULL ) {
                    qlist.push( lists[i]->val ) ;
                    lists[i] = lists[i]->next;
                }
            }
            ListNode* head = new ListNode(0);
            ListNode* p =head ;
            while( qlist.size() ) {
                ListNode *temp = new ListNode( qlist.top() ) ;
                p->next = temp ;
                p = p->next ;
                qlist.pop() ;
            }
            return head -> next ;
        }
    };
    

    Complexity Analysis

    • Time complexity: $O(MNlogN)$. When we save the element to heap will take us $O(MNlogN)$.
      Pop operation will take us $O(MNlogN)$.So total time is $O(MN+2MNlogN)$
    • Space complexity : $O(M*N)$.
      ####Approach #3 Divide and conquer[Accepted]

    Algorithm

    Like the merge sort . we can divide the lists to two part then merge each two lists .
    and we will still use the function ( merge two lists ).

    c++

    class Solution {
    public:
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
            ListNode* head = new ListNode(0) ;
            ListNode* p = head ;
            while( l1 != NULL && l2 != NULL ) {
                if( l1->val <= l2->val ) {
                    p->next = l1 ;
                    p = p->next ;
                    l1 = l1->next ;
                }
                else {
                    p->next = l2 ;
                    p = p->next ;
                    l2 = l2->next ;
                }
            }
            if( l1 != NULL ) {
                p->next = l1 ;
            }
            else if( l2 != NULL ) {
                p->next = l2 ;
            }
            return head->next;
        }
        ListNode* divide_and_conquer(vector< ListNode* >& lists , int left , int right  ) {
            if(left == right ) {
                return lists[left];
            }
            int mid = (right - left ) / 2 + left ;
            return mergeTwoLists( divide_and_conquer( lists , left , mid )  , divide_and_conquer( lists , mid + 1 ,right ) ) ;
        }
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            if( lists.size() == 0 ) return NULL;
            return divide_and_conquer( lists , 0 , lists.size() - 1 ) ;
        }
    };
    

    Complexity Analysis

    • Time complexity: $O(MNlogN)$. Compare to the approach #1 ,we cut the lists to two parts will $O(N)->O(logN)$
    • Space complexity : $O(1)$.

Log in to reply
 

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