Share my ugly C++ solution in 44ms


  • 0
    G

    1. Check the heads of all lists, find the minimum value

    2. If more than one lists have the head with the minimum value, merge all minimum nodes to the first list

    3. After one loop, append all minimum value nodes to the result

    4. Goto next loop until all lists reach tail nodes


    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int count = lists.size();
        if (0 == count) return NULL;
        if (1 == count) return lists[0];
        ListNode* p = NULL;
        ListNode* cur = NULL;
        while (true) {
            int k = -1;
            int min_val = 0x7FFFFFFF;
            for (int i = 0; i < count; ++i) {
                // list reach tail
                if (!lists[i]) continue;
                if (lists[i]->val < min_val) {
                    // find smaller value, k = i
                    min_val = lists[i]->val;
                    k = i;
                } else if (lists[i]->val == min_val) {
                    if (k >= 0) {
                        // find the same minimum value
                        // insert the head node of lists[i] to lists[k]
                        // then move lists[i] to next
                        // e.g.
                        //     lists[k] = [1,3,5,7,9], lists[i] = [1,1,4,5,7]
                        // =>  lists[k] = [1,1,1,3,5,7,9], lists[i] = [4,5,7]
                        while (lists[i] && lists[i]->val == min_val) {
                            ListNode* next = lists[i]->next;
                            lists[i]->next = lists[k]->next;
                            lists[k]->next = lists[i];
                            lists[i] = next;
                        }
                    } else {
                        // lists[0].val == 0x7FFFFFFF
                        k = i;
                    }
                }
            }
            if (k >= 0) {
                // if k >= 0, find next node, else all lists reach tail
                if (cur) {
                    cur->next = lists[k];
                    cur = lists[k];
                    lists[k] == lists[k]->next;
                } else {
                    cur = lists[k];
                    p = lists[k];
                    lists[k] == lists[k]->next;
                }
                while (lists[k] && lists[k]->val == min_val) {
                    cur = lists[k];
                    lists[k] = lists[k]->next;
                }
            } else {
                // all lists reach tail
                break;
            }
        }
        return p;
    }

Log in to reply
 

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