Start learning free

LESSON 322 OF 442 · LINKED LISTS

Merge K Sorted Lists in Kotlin: O(n × k) by Scanning the Heads

Practice O(n × 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] <= 107
  • 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 × k) time and use O(1) extra space apart from the merged list's new nodes (one per value), where n is the total number of nodes across all lists and k is the number of lists.
(A faster O(n log k) solution, with a min-heap, has its own lesson.)


Hints:

The output is sorted: at every moment you only need the smallest current head across all lists.
What's the simplest way to find it?

Use a dummy sentinel node and a tail walker.
Each iteration: scan all k heads, pick the smallest, append a new node with its value after tail, move tail onto it, and advance the chosen list. Repeat until every list is exhausted.

We produce n output nodes, and each one costs an O(k) scan of all heads — Time Complexity is O(n × k).
Apart from the merged list it returns (one new node per value), the solution keeps only the dummy node and a few variables, so the Extra Space is O(1).
STEP 1 OF 14
    Ctrl + Enter to check

    KOTLIN · LINKED LISTS

    Merge K Sorted Lists in Kotlin, explained

    Problem overview

    mergeKLists(lists) receives an Array<ListNode?>: k singly linked lists, each sorted in ascending order, where a null entry stands for an empty list. It must return the head of one sorted list that contains every value from all of them, or null if there are no values at all.

    For the lists 1 → 4 → 5, 1 → 3 → 4 and 2 → 6, the result is 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6. For lists = [], and for a single empty list, the result is an empty list, null.

    The lesson asks for O(n × k) time, where n is the total number of nodes and k is the number of lists. Apart from the nodes of the answer, it uses constant extra space. A faster version with a heap has its own lesson.

    Approach: always take the smallest head

    Each input list is sorted, so its smallest unused value is always the node at its front, its head. The smallest value among all unused values is therefore the smallest of the k heads. Repeating "pick the smallest head, append it to the answer, move that list forward" produces the values in order, until every list is exhausted.

    Finding the smallest head is the simple part: look at all k heads and compare. That scan costs O(k), and it happens once for each of the n output nodes, which is where O(n × k) comes from.

    Two supporting tricks keep the code short. A dummy node placed before the answer means the first appended node needs no special case: the answer is always dummy.next. A tail variable points at the last node appended, so each new node is attached with tail.next.

    On [[1, 4, 5], [1, 3, 4], [2, 6]] the heads at the start are 1, 1 and 2. The first list's 1 is picked, because the comparison is strict and the first of equal heads wins. The heads become 4, 1, 2, so the second list's 1 is next, then 2, then 3. The heads are then 4, 4 and 6, and so on, ending with the lone 6 once the other two lists are empty. The output is 1, 1, 2, 3, 4, 4, 5, 6.

    Step by step

    1. Create the dummy node. val dummy = ListNode() is a placeholder whose value never matters.
    2. Create the tail. var tail = dummy points at the end of the answer so far. It is a var because it moves with every appended node.
    3. Loop while any list has nodes. The helper anyNonNull(lists), written at the end, answers that.
    4. Start with no winner. var ind = -1 will hold the index of the list with the smallest head.
    5. Scan every list. for (i in lists.indices) visits each position of the array.
    6. Update the winner. A list competes only if it isn't null. It wins if no winner is chosen yet, or if its head is strictly smaller than the current winner's.
    7. Append a new node with the winner's value to the end of the answer.
    8. Advance the winning list by replacing its entry in the array with the next node.
    9. Move tail onto the node just added.
    10. Return dummy.next once the loop ends: the head of the merged list, or null if nothing was appended.
    11. Write the helper. anyNonNull loops over the array and returns true at the first entry that isn't null.
    12. Finish the helper with false after the loop, since every entry was null.

    The solution in Kotlin

    class Solution {
    fun mergeKLists(lists: Array<ListNode?>): ListNode? {
        val dummy = ListNode()
        var tail = dummy
        while (anyNonNull(lists)) {
            var ind = -1
            for (i in lists.indices) {
                if (lists[i] != null && (ind == -1 || lists[i]!!.`val` < lists[ind]!!.`val`)) {
                    ind = i
                }
            }
            tail.next = ListNode(lists[ind]!!.`val`)
            lists[ind] = lists[ind]!!.next
            tail = tail.next!!
        }
        return dummy.next
    }

    private fun anyNonNull(lists: Array<ListNode?>): Boolean {
        for (l in lists) {
            if (l != null) {
                return true
            }
        }
        return false
    }
}

    Kotlin details worth a look:

    • Nullable types. ListNode? means a node or null. The array's elements are nullable, and so is next.
    • Why !! appears. The compiler doesn't smart-cast an array element after a null check. Even right after if (lists[i] != null), writing lists[i].`val` is rejected with only safe (?.) or non-null asserted (!!.) calls are allowed on a nullable receiver of type 'ListNode?'. The !! says "I know this isn't null", and it would throw if that were wrong. Here it is safe, because the loop condition guarantees that some list is non-null, and the scan only picks non-null entries.
    • The backticks around val. The node's field is named val, which is a Kotlin keyword, so it has to be written in backticks every time it is used.
    • Short-circuit evaluation. In ind == -1 || lists[ind]!!.`val` ..., the right side runs only when ind is not -1. Without that guard, lists[-1] would throw.
    • tail = tail.next!!. next was just assigned, so it can't be null. tail keeps the type ListNode from the line that created it.
    • private fun keeps the helper out of the class's public surface.
    • The input array is used up. Step 8 overwrites entries of lists, so after the call every entry is null. The nodes themselves are not changed, because the answer is built from new nodes created with the same values.

    Complexity

    Time: O(n × k). The outer loop runs once per output node, n times. Each run scans the k entries to find the smallest head, and anyNonNull does at most another k checks. That is O(k) per node.

    Space: O(1) extra. The only memory beyond the answer's own nodes is the dummy node and a few variables. The answer needs n new nodes, which the lesson doesn't count as extra.

    Edge cases and common mistakes

    • No lists at all. With lists = [], anyNonNull is false immediately, and dummy.next is still null.
    • Only empty lists. [null] behaves the same way, and so does [null, null].
    • Some lists empty. [null, 1 → 5, null, 3] merges to 1 → 3 → 5. The scan skips null entries.
    • Equal values. Duplicates across lists are all kept. Whichever of equal heads is chosen, the output values are the same.
    • Dropping the ind == -1 test. Comparing with lists[ind] before any winner exists would index -1.
    • Forgetting to advance the list. If step 8 is skipped, the same head is chosen forever and the loop never ends.
    • Comparing the nodes instead of their values. lists[i]!! < lists[ind]!! doesn't compile. Compare the val fields.

    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.
    • [null, -3 → 7, null, 0] gives -3 → 0 → 7.
    • [2 → 2, 2] gives 2 → 2 → 2.
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free