C++ solution using Merge Sort


  • 9
    H
    class Solution {
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            return partition(lists, 0, lists.size()-1);
        }
        
        ListNode* partition(vector<ListNode*>& lists, int start, int end){
            if(start == end){
                return lists[start];
            }
            
            if(start < end){
                int mid = (end+start)/2;
                
                ListNode* l1 = partition(lists, start, mid);
                ListNode* l2 = partition(lists, mid+1, end);
                return merge(l1, l2);
            }
            
            return NULL;
        }
        
        ListNode* merge(ListNode* l1, ListNode* l2){
            if(!l1) return l2;
            if(!l2) return l1;
            
            if(l1->val < l2->val){
                l1->next = merge(l1->next, l2);
                return l1;
            }else{
                l2->next = merge(l1, l2->next);
                return l2;
            }
        }
    };

Log in to reply
 

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