My C++ solution with Divide and Conquer(Runtime == 23ms, beats 99.74%)


  • 0
    C

    0_1498716069064_WechatIMG1.jpeg

    • If you don't know Divide and Conquer, try to google it.
    • Then just read the code.
    • It's my first submission.Thanks for reading and replying!
    class Solution {
    public:
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
            ListNode *head = new ListNode(0);
            ListNode *q = head;
            
            while(l1 && l2){
                if(l1->val <= l2->val){
                    q->next = l1;
                    l1 = l1->next;
                }else{
                    q->next = l2;
                    l2 = l2->next;
                }
                q = q->next;
            }
            if(l1) q->next = l1;
            if(l2) q->next = l2;
            
            return head->next;
        }
        ListNode* mergeLists(vector<ListNode*>& lists, int low, int high){
            if(low == high) return lists[low];
            if(low == high - 1){
                return mergeTwoLists(lists[low], lists[high]);
            }
            int mid = (low + high) >> 1;
            return mergeTwoLists(mergeLists(lists, low, mid), mergeLists(lists, mid+1, high));
        }
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            if(lists.size() == 0) return NULL;
            int len = lists.size();
            return mergeLists(lists, 0, len-1);
        }
    };
    

Log in to reply
 

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