23. Merge k Sorted Lists

Problem

https://leetcode.com/problems/merge-k-sorted-lists/

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Solution

Solution0

A straight forward solution would be ((lsit1 + list2) + list3) + list4 ....

The time complexity would be:
O(2n + 3n + 4n + ... + kn) =>
O(n * ((2+k) * (k-1) / 2)) =>
O(n * k^2)

Solution1

Store the first item of every list in a Priority Queue. The head of the queue would be the smallest.

Adding an item into a priority queue takes O(logk), so the time complexity would be O(n * k * logk)

/**
 * 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
    }

    function PriorityQueue(compare) {
        this._heap = []
        this._compare = typeof compare === 'function'? compare : function(a, b) {
            return a - b
        }
    }

    PriorityQueue.prototype.shift = function shift() {
        let heap = this._heap
        let compare = this._compare

        // empty heap
        if (heap.length <= 0) { return }

        // the root has the highest priority
        let result = heap[0]
        // put the last node(lowest priority) onto the root
        heap[0] = heap[heap.length-1]
        heap.length -= 1
        // then heapify top down
        heapify(0)

        function heapify(i) {
            // assume this node has the highest priority
            let max = i

            // then check its left and right children
            let left = i * 2 + 1
            if (left < heap.length && compare(heap[left], heap[max]) > 0) {
                max = left
            }

            let right = i * 2 + 2
            if (right < heap.length && compare(heap[right], heap[max]) > 0) {
                max = right
            }

            // swap the higher child up then check the new child
            if (max !== i) {
                let t = heap[max]
                heap[max] = heap[i]
                heap[i] = t
                heapify(max)
            }
        }

        return result
    }

    PriorityQueue.prototype.push = function push(item) {
        let heap = this._heap
        let compare = this._compare

        // put the new node in lowest priority
        heap[heap.length] = item

        // then heapify bottom up
        let i = heap.length - 1
        while (i > 0) {
            let parent = Math.floor((i - 1) / 2)

            // parent has higher priority, end of heapify
            if (compare(heap[parent], heap[i]) >= 0) {
                break
            }

            // otherwise swap the value
            let t = heap[i]
            heap[i] = heap[parent]
            heap[parent] = t

            // pop the node up
            i = parent
        }
    }

    PriorityQueue.prototype.isEmpty = function isEmpty() {
        return this._heap.length <= 0
    }




    let minQueue = new PriorityQueue(function(nodeA, nodeB) {
        return nodeB.val - nodeA.val
    })

    let result = new ListNode(null)
    let p = result

    // push the first node of each list into the queue
    for (let i = 0; i < lists.length; i += 1) {
        if (lists[i]) {
            minQueue.push(lists[i])
        }
    }

    while (!minQueue.isEmpty()) {
        let node = minQueue.shift()
        p.next = new ListNode(node.val)
        p = p.next
        if (node.next) {
            minQueue.push(node.next)
        }
    }

    if (result.next) {
        // dump the first node
        return result.next
    } else {
        return null
    }
};

Solution2

Divide and Conquer.

Keep dividing the lists into two parts until there are only two left, then merge them back.

The time complexity would be:
T(k) = 2 * T(k/2) + O(n*k)
O(k^(log2)) = O(k) < O(n*k)
So T(k) = O(n * k * logk)

/**
 * 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
    }

    return mergeHelper(0, lists.length-1)

    function mergeHelper(index1, index2) {
        if (index1 === index2) {
            return lists[index1]
        }

        let midIndex = Math.floor(index1 + (index2 - index1) / 2)
        return mergeTwoLists(mergeHelper(index1, midIndex), mergeHelper(midIndex+1, index2))

        function mergeTwoLists(list1, list2) {
            let result = new ListNode(null)
            let p = result

            while(list1 || list2) {
                let node = new ListNode(null)
                if (!list1) {
                    node.val = list2.val
                    list2 = list2.next
                } else if (!list2) {
                    node.val = list1.val
                    list1 = list1.next
                } else {
                    if (list1.val < list2.val) {
                        node.val = list1.val
                        list1 = list1.next
                    } else {
                        node.val = list2.val
                        list2 = list2.next
                    }
                }
                p.next = node
                p = p.next
            }

            if (result.next) {
                return result.next
            } else {
                return null
            }
        }
    }
};