23.merge-k-sorted-lists.md

23. Merge k Sorted Lists

For merging two sorted linked list, see 21. Merge Two 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 ->
        result = mergeTwoLists(result, head)
    }
    return result
}

• Time Complexity: O(k * N) for N is total number of nodes in the result, and k is the number of lists.
• Space Complexity: O(N) for result.

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.

size = 5
1, 2, 3, 4, 5, _
^^^^  ^^^^  ^^^^
\  /  \  /  \  /
 12    34    5
 ^^^^^^^^    ^
   \  /      |
   1234      5
   ^^^^^^^^^^^
     \     /
      12345

fun conquer(lists: List<ListNode?>): ListNode? {
    if (lists.isEmpty()) return null
    if (lists.size == 1) return lists.first()

    val merged = mutableListOf<ListNode?>()
    val n = lists.size
    var i = 0
    // We merge (0, 1), (2, 3), (4, 5), ...
    while (i < n) {
        val first = lists[i]
        val second: ListNode? = if (i + 1 < n) lists[i + 1] else null
        merged.add(mergeTwoLists(first, second))
        i += 2
    }
    return conquer(merged)
}

// 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 * log k)
  • We merge (0, 1), (2, 3), (4, 5), ... in each level, producing k / 2 lists until 1 list, recursion depth is log k.
• Space Complexity: O(N) for result + O(log k) for recursion stack.

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(k log k + N log k)
  • O(k log k) to add all head of k lists into priority queue.
  • O(N log k) to poll N nodes from priority queue.
• Space Complexity: O(k).
  • The priority queue stores at most one node from each of the k lists.