C++ solution using Merge Sort

  • 9
    class Solution {
        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;
                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.