My JavaScript Solution Based on Heap


  • 0
    D
    /**
     * Definition for singly-linked list.
     * function ListNode(val) {
     *     this.val = val;
     *     this.next = null;
     * }
     */
    /**
     * @param {ListNode[]} lists
     * @return {ListNode}
     */
    var mergeKLists = function(lists) {
        if (lists.length === 0) {
            return null;
        }
        var result = null;
        var tail = null;
        for (var i = 0; i < lists.length; i++) {
            if (lists[i] === null) {
                lists[i] = new ListNode(Number.POSITIVE_INFINITY);
            }
        }
        build_min_heap(lists, lists.length, 0);
        var rootValue = lists[0].val;
        while (isFinite(rootValue)) {
            if (result === null) {
                result = new ListNode(rootValue);
                tail = result;
            }
            else {
                tail.next = new ListNode(rootValue);
                tail = tail.next;
            }
            lists[0] = lists[0].next;
            if (lists[0] === null) {
                lists[0] = new ListNode(Number.POSITIVE_INFINITY);
            }
            min_heapify(lists, lists.length, 0);
            rootValue = lists[0].val;
        }
        return result;
    };
    
    function swap_in_array(A, i, j) {
        var temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
    
    function min_heapify(A, arr_length, i) {
        var l = 2 * i + 1,
            r = 2 * i + 2,
            smallest = i;
        if (l < arr_length && A[l].val < A[smallest].val) {
            smallest = l;
        }
        if (r < arr_length && A[r].val < A[smallest].val) {
            smallest = r;
        }
        if (smallest !== i) {
            swap_in_array(A, i, smallest);
            min_heapify(A, arr_length, smallest);
        }
    }
    
    function build_min_heap(A, arr_length, i) {
        var l = 2 * i + 1,
            r = 2 * i + 2;
        if (l < arr_length) {
            build_min_heap(A, arr_length, l);
        }
        if (r < arr_length) {
            build_min_heap(A, arr_length, r);
        }
        min_heapify(A, arr_length, i);
    }
    

    Time complexity is alt text


Log in to reply
 

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