23.merge-k-sorted-lists.md

23. Merge k Sorted Lists

Sorting

fun mergeKLists(lists: Array<ListNode?>): ListNode? {
    // Chain all linked list as one array list
    val itemList = mutableListOf<Int>()
    lists.forEach { list -> 
        var node: ListNode? = list
        while (node != null) {
            itemList.add(node!!.`val`)
            node = node!!.next
        }
    }
    // Sort that array list
    itemList.sort()

    // Create the result linked list from the sorted array list
    val sentinel = ListNode(0)
    var node: ListNode? = sentinel
    for (i in 0 until itemList.size) {
        node?.next = ListNode(itemList[i])
        node = node?.next
    }
    return sentinel.next
}

• Time Complexity: O(n lg n), for n is total number of nodes.
• Space Complexity: O(n) for saving all nodes.

Merge One By One

fun mergeKLists(lists: Array<ListNode?>): ListNode? {
    var result: ListNode? = null
    lists.forEach { head ->
        if (result == null) {
            result = head
        } else {
            result = mergeTwoLinkedList(result, head)
        }
    }
    return result
}

private fun mergeTwoLinkedList(list1: ListNode?, list2: ListNode?): ListNode? {
    val sentinel = ListNode(0)
    var result: ListNode? = sentinel
    var node1: ListNode? = list1
    var node2: ListNode? = list2

    while (node1 != null && node2 != null) {
        if (node1.`val` < node2.`val`) {
            result?.next = node1
            node1 = node1.next
        } else {
            result?.next = node2
            node2 = node2.next
        }
        result = result?.next
    }
    result?.next = if (node1 == null) node2 else node1
    return sentinel.next
}

• Time Complexity: O(k * N) for N is total number of nodes in the result.
• Space Complexity: O(N) for result / O(1) if we can modify the function argument.

Divide & Conquer

We will merge each two lists into one, so k lists will be k/2 lists, repeat until it becomes one sorted list.

fun mergeKLists(lists: Array<ListNode?>): ListNode? {
    if (lists.isEmpty()) return null
    if (lists.size == 1) return lists[0]
    var i = 0
    val results = mutableListOf<ListNode?>()
    
    // Merge (0, 1), (2, 3), (4, 5), ...
    while (i < lists.size) {
        if (i + 1 < lists.size) {
            results.add(merge(lists[i], lists[i + 1]))
        } else {
            results.add(lists[i])
        }
        i += 2
    }
    return mergeTwo(results)
}

// Or we can use the idea from merge sort, break the list into half, and merge them
fun mergeKLists(lists: Array<ListNode?>): ListNode? {
    // Base cases
    if (lists.isEmpty()) return null
    if (lists.size == 1) return lists[0]

    // size = 3 / 2 = 1
    // [0] | [1 2]
    // size = 2 / 2 = 1
    // [0] | [1] 
    val middle = lists.size / 2
    val left = divide(lists.sliceArray(0 until middle))
    val right = divide(lists.sliceArray(middle until lists.size))
    return merge(left, right) // As same as `mergeTwoLinkedList()` function
}

• Time Complexity: O(N * lg k)
• Space Complexity: O(N) for result / O(1) if we can modify the function argument.

Priority Queue

We add all head into priority queue, and poll the minimum value and put its next pointer into the queue.

fun mergeKLists(lists: Array<ListNode?>): ListNode? {
    val sentinel = ListNode(-1)
    var current: ListNode = sentinel
    val minHeap = PriorityQueue<ListNode>() { n1, n2 -> n1.`val` - n2.`val` }
    for (list in lists) {
        if (list != null) minHeap.add(list)
    }
    while (minHeap.isNotEmpty()) {
        val node = minHeap.poll()
        if (node.next != null) minHeap.add(node.next)
        current.next = node
        current = current.next
    }

    return sentinel.next
}

• Time Complexity: O(lg k) for insert and poll operations of priority queue, and there are N total nodes, so it takes O(N lg k) time.
• Space Complexity: O(k) for priority queue.