Beat 100% of submissions


  • 0
    A
    ListNode* mergeTwo(ListNode* list1, ListNode* list2) {
        ListNode* prev = NULL;
        ListNode* head = NULL;
        while (list1 != NULL || list2 != NULL) {
            ListNode** p;
            if (list1 != NULL && list2 != NULL) {
                if (list1->val < list2->val) {
                    p = &list1;
                } else {
                    p = &list2;
                }
            } else if (list1 == NULL) {
                p = &list2;
            } else {
                p = &list1;
            }
            
            if (prev == NULL) {
                head = *p;
                prev = head;
            } else {
                prev->next = *p;
                prev = *p;
            }
            (*p) = (*p)->next;
        }
        if (prev != NULL) prev->next = NULL;
        return head;
    }
    
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.size() == 0) return NULL;
        for (int d=1;d < lists.size();d*=2) {
            for (int i=0;i < lists.size();i += 2*d) {
                if (i+d < lists.size()) {
                    lists[i] = mergeTwo(lists[i], lists[i+d]);
                }
            }
        }
        return lists[0];
    }

Log in to reply
 

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