C99 solution, using heap.


  • 0
    F
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
    void push(int *heapVal, int *heapInd, int val, int ind, int *top) {
        heapVal[*top] = val;
        heapInd[*top] = ind;
        ++*top;
        int cur = *top - 1, root = cur / 2;
        while (root && heapVal[cur] < heapVal[root]) {
            int tmp = heapVal[cur];
            heapVal[cur] = heapVal[root];
            heapVal[root] = tmp;
            tmp = heapInd[cur];
            heapInd[cur] = heapInd[root];
            heapInd[root] = tmp;
            cur = root;
            root = cur / 2;
        }
    }
    int pop(int *heapVal, int *heapInd, int *top) {
        int res = heapInd[1];
        --*top;
        heapVal[1] = heapVal[*top];
        heapInd[1] = heapInd[*top];
        int root = 1, left = 2, right = 3;
        while (left < *top) {
            int target = left;
            if (right < *top && heapVal[right] < heapVal[left]) target = right;
            if (heapVal[root] <= heapVal[target]) break;
            int tmp = heapVal[root];
            heapVal[root] = heapVal[target];
            heapVal[target] = tmp;
            tmp = heapInd[root];
            heapInd[root] = heapInd[target];
            heapInd[target] = tmp;
            root = target;
            left = 2 * root;
            right = left + 1;
        }
        return res;
    }
    struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
        if (listsSize < 1) return 0;
        if (listsSize < 2) return lists[0];
        int *heapVal = malloc((listsSize + 1) * sizeof(int)), *heapInd = malloc((listsSize + 1) * sizeof(int));
        int top = 1;
        int i;
        for (i = 0; i < listsSize; i++) {
            if (lists[i]) push(heapVal, heapInd, lists[i]->val, i, &top);
        }
        struct ListNode dummy, *p = &dummy;
        p->next = 0;
        while (top != 1) {
            int ind = pop(heapVal, heapInd, &top);
            p->next = lists[ind];
            p = p->next;
            if (p->next) {
                lists[ind] = p->next;
                push(heapVal, heapInd, lists[ind]->val, ind, &top);
            }
        }
        free(heapVal);
        free(heapInd);
        return dummy.next;
    }
    

Log in to reply
 

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