Share my 'Divide-and-Conquer' c++ code,only use 38ms , and it is so easy to understand


  • -1
    S
    class Solution {
        public:
            ListNode *mergeKLists(vector<ListNode *> &lists) {
                return merge(lists,0,lists.size() -1);
            }
    
            ListNode *merge(vector<ListNode *> &lists,int left,int right){
                if(left > right)return NULL;
                if(left == right)return lists[left];
                int mid = (left + right)/2;
                ListNode *first = merge(lists,left,mid);
                ListNode *second = merge(lists,mid + 1,right);
    
                if(first == NULL)return second;
                if(second == NULL)return first;
    
                ListNode *head = NULL;
                ListNode *ptr = NULL;
                ListNode *pre = NULL;
    
                while(first && second){
                    if(first->val < second->val){
                        ptr = first;
                        first = first->next;
                    }else{
                        ptr = second;
                        second = second->next;
                    }
                    if(NULL == head){
                        head = ptr;
                        pre = ptr;
                        continue;
                    }
                    pre->next = ptr;
                    pre = ptr;
                }
                if(first)pre->next = first;
                if(second)pre->next = second;
                return head;
            }
    
    };

  • 0
    O

    I run your code. it works but take 414ms. not so fast as you claimed


Log in to reply
 

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