Start learning free

LESSON 286 OF 348 · LINKED LISTS

Merge K Sorted Lists in Kotlin: O(n log k) with a Min-Heap

Practice O(N log k) Read the full explanation

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

 

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

 

Constraints:

  • k == lists.length
  • 0 <= k <= 104
  • 0 <= lists[i].length <= 500
  • -104 <= lists[i][j] <= 104
  • lists[i] is sorted in ascending order.
  • The sum of lists[i].length will not exceed 104.
Note:

Your algorithm should run in O(n log k) time and use O(k) extra space, where n is the total number of nodes across all lists and k is the number of lists.


Hints:

The brute force re-scans every list head each time. What data structure gives you the smallest of k values in O(log k) instead of O(k)?

Use a min-heap seeded with the head of every non-empty list, ordered by node.val.
Each iteration: extract the smallest node, append a copy of its value to the merged tail, and if it has a successor, push that successor onto the heap.
When the heap is empty, every list has been fully consumed.

The heap holds at most k nodes at any time. Each of the n output nodes costs one extract and at most one insert, each O(log k) — Time Complexity is O(n log k).
The heap itself uses O(k) extra space.

STEP 1 OF 11
    Ctrl + Enter to check

    KOTLIN · LINKED LISTS

    Merge K Sorted Lists in Kotlin, explained

    Problem overview

    The function mergeKLists receives an array lists of k linked lists, each sorted in ascending order. It must merge them into one sorted linked list and return its head. Some of the lists can be empty (null), and the array itself can be empty.

    For [[1,4,5],[1,3,4],[2,6]] the merged list is [1,1,2,3,4,4,5,6]. For [] and for [[]] the answer is an empty list.

    The statement asks for O(n log k) time and O(k) extra space, where n is the total number of nodes.

    Approach: always take the smallest of the k fronts

    Each list is sorted, so the smallest unmerged value overall is one of the k current front nodes. The simplest solution scans all k fronts to find the minimum, appends it and repeats. That costs O(k) per output node, so O(n * k) in total.

    A min-heap does the same job faster. A heap is a container that always gives back its smallest element, and it needs O(log k) time for both insertion and removal. The heap holds at most one node per list: the current front. Take the smallest from the heap, append it to the output, and put that node's successor in the heap. The heap never holds more than k nodes, and each of the n output nodes costs one removal and at most one insertion, which gives O(n log k).

    Step by step

    1. Create the heap as a java.util.PriorityQueue<ListNode> called minNodes, ordered by each node's val. The comparator compareBy { it.`val` } sorts ascending, so the smallest value is on top.
    2. Loop over the heads in lists.
    3. Add every non-null head to the heap. Empty lists contribute nothing.
    4. Create a dummy node, val dummy = ListNode(). The merged list is built after it, so the first appended node needs no special case.
    5. Keep a walker, var tail = dummy, always pointing at the last node appended.
    6. Loop while the heap isn't empty. Each iteration takes one node out of the heap.
    7. Poll the smallest node into minNode.
    8. Append a new node with minNode.`val` as tail.next. The output is built from new nodes, so the input lists are left unchanged.
    9. Add the successor to the heap if minNode.next exists. A list keeps feeding the heap one node at a time until it runs out.
    10. Advance the walker with tail = tail.next!!.
    11. Return dummy.next, the head of the merged list. For no input nodes it is null.

    The solution in Kotlin

    class Solution {
    fun mergeKLists(lists: Array<ListNode?>): ListNode? {
        val minNodes = java.util.PriorityQueue<ListNode>(compareBy { it.`val` })
        for (head in lists) {
            if (head != null) {
                minNodes.add(head)
            }
        }
        val dummy = ListNode()
        var tail = dummy
        while (minNodes.isNotEmpty()) {
            val minNode = minNodes.poll()
            tail.next = ListNode(minNode.`val`)
            if (minNode.next != null) {
                minNodes.add(minNode.next)
            }
            tail = tail.next!!
        }
        return dummy.next
    }
}

    The Kotlin details worth knowing:

    • Using a Java class. Kotlin runs on the JVM and can use Java's standard library directly. java.util.PriorityQueue is Java's binary heap. Written with its full name, it needs no import.
    • compareBy. It builds a Comparator from a function that picks the sort key. compareBy { it.`val` } orders nodes by their val, ascending. The type of it is inferred from the queue's element type, ListNode.
    • Backticks for val. val is a keyword, but the node's field has that name, so it is written it.`val`.
    • Ties. Nodes with equal values may come out of the heap in any order. Since only the values are copied into the output, the result is the same either way.
    • Platform types. Java methods like poll() return a type that Kotlin doesn't mark nullable, so minNode is used without !!. In this loop the heap is known to be non-empty, so poll() always returns a node. Likewise minNodes.add(minNode.next) compiles even though next is nullable, because the Java parameter type accepts it, and the if guarantees it isn't null here.
    • tail.next!!. next is a nullable property, and the compiler doesn't track that the previous line assigned it, so !! asserts it is not null.
    • The type Array<ListNode?>. It's an array of nullable nodes, so head in the loop may be null and the check is needed.

    Complexity

    Time: O(n log k). Building the heap takes at most k insertions of O(log k) each. After that, each of the n output nodes costs one poll and at most one insertion, each O(log k).

    Space: O(k) extra. The heap never holds more than one node per list. The output list has n new nodes, but that is the result itself.

    Edge cases and common mistakes

    • No lists. arrayOf() leaves the heap empty, the loop never runs and the function returns null.
    • Only empty lists. [null] adds nothing to the heap, with the same result.
    • Some empty lists. [null, [2], null, [-1, 9]] gives [-1, 2, 9]. The null check on each head keeps null out of the heap.
    • Negative values and duplicates. The comparator handles both. Equal values simply appear next to each other in the output.
    • Forgetting to add the successor. The output would contain only the first node of each list.
    • Adding a null successor. A PriorityQueue throws on null, so the check on minNode.next matters.
    • Returning dummy. That includes the placeholder node with value 0 at the front.

    Testing

    • [[1,4,5],[1,3,4],[2,6]] gives [1,1,2,3,4,4,5,6].
    • [] gives an empty list (null).
    • [[]] gives an empty list.
    • [[], [2], [], [-1, 9]] gives [-1, 2, 9].
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free