Start learning free

LESSON 310 OF 414 · LINKED LISTS

Merge K Sorted Lists in Scala: O(n log k) with a PriorityQueue

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 the node's value.
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

    SCALA · LINKED LISTS

    Merge K Sorted Lists in Scala, explained

    Problem overview

    The method mergeKLists receives an Array[ListNode] named lists. Each element is the head of a linked list sorted in ascending order, and an element may be null when its list is empty. The method must merge all the lists into one sorted list and return its head.

    For lists = [[1,4,5],[1,3,4],[2,6]] the merged list is [1,1,2,3,4,4,5,6]. For an empty array the answer is the empty list, and for [[]], an array holding one empty list, it is also empty. The statement asks for O(n log k) time and O(k) extra space, where n is the total number of nodes and k is the number of lists.

    Approach: always take the smallest head

    The smallest remaining value overall must be the head of one of the lists, because each list is sorted. So the merge repeats one step: take the smallest head, append it to the result, and replace it with its successor in its own list.

    The cost depends on how you find the smallest head. Scanning all k heads each time costs O(k) per output node, which gives O(n * k) overall. A min-heap (a priority queue that gives back the smallest element first) does the same job in O(log k): it holds at most one node per list, so it never has more than k elements, and each of the n output nodes costs one removal and at most one insertion. That is where O(n log k) comes from.

    Step by step

    1. Create the heap and name it minNodes. It is a scala.collection.mutable.PriorityQueue[ListNode], written with its full package name because nothing is imported. Scala's PriorityQueue is a max-heap: it gives back the largest element first. To get the smallest value first, the ordering passed in a second argument list is scala.math.Ordering.by[ListNode, Int](node => node.`val`).reverse. Ordering.by compares nodes through their val field, and .reverse flips the order. The field name needs backticks, since val is a Scala keyword.
    2. Visit each head with for (head <- lists).
    3. Skip empty lists. If head is not null, call enqueue(head).
    4. Create a sentinel, val dummy = new ListNode(). The merged list is built after it.
    5. Keep a tail, var tail = dummy, always pointing at the last appended node.
    6. Loop while minNodes.nonEmpty. Each iteration costs O(log k).
    7. Take the smallest node with val minNode = minNodes.dequeue().
    8. Append a new node holding minNode.`val`: tail.next = new ListNode(minNode.`val`).
    9. Feed the heap. If minNode.next is not null, enqueue it. Each list supplies one node at a time until it runs out.
    10. Advance the tail: tail = tail.next.
    11. Return dummy.next as the last expression, the head of the merged list.

    The solution in Scala

    class Solution {
    def mergeKLists(lists: Array[ListNode]): ListNode = {
        val minNodes = scala.collection.mutable.PriorityQueue[ListNode]()(scala.math.Ordering.by[ListNode, Int](node => node.`val`).reverse)
        for (head <- lists) {
            if (head != null) {
                minNodes.enqueue(head)
            }
        }
        val dummy = new ListNode()
        var tail = dummy
        while (minNodes.nonEmpty) {
            val minNode = minNodes.dequeue()
            tail.next = new ListNode(minNode.`val`)
            if (minNode.next != null) {
                minNodes.enqueue(minNode.next)
            }
            tail = tail.next
        }
        dummy.next
    }
}

    The Scala details worth knowing:

    • Two argument lists. PriorityQueue[ListNode]()(ordering) has an empty first list for the initial elements, and a second list for the ordering, which is normally supplied implicitly. Here the ordering is given explicitly.
    • Max-heap by default. PriorityQueue(3, 1, 2).dequeue() returns 3. Passing Ordering.Int.reverse makes it return 1. The same idea, applied to a field, is Ordering.by(...).reverse.
    • Why the ordering is needed. There is no default ordering for ListNode, so the compiler needs one to build a PriorityQueue[ListNode].
    • for (head <- lists) loops over the elements of an array. It is not a counted loop and has no index.
    • Empty array. for does nothing for an array with no elements, and the heap stays empty.
    • The input is not modified. The code builds new nodes with new ListNode(minNode.`val`) instead of relinking the existing ones, so the input lists stay as they were. This costs n new nodes, which the output needs anyway.
    • The last expression is the result. dummy.next needs no return.

    Complexity

    Time: O(n log k). The heap holds at most k nodes. Every one of the n nodes is enqueued once and dequeued once, and each of these operations takes O(log k). The initial loop over the heads adds at most k insertions, which is no more than n when there are no empty lists.

    Space: O(k) extra for the heap. The output list takes n nodes, which is the result rather than working memory.

    Edge cases and common mistakes

    • No lists. lists = [] leaves the heap empty, so the loop never runs and dummy.next is null.
    • Empty lists inside the array. A null element must not be enqueued: comparing it would fail with a NullPointerException. The check in the first loop handles [[]] and arrays that mix empty and non-empty lists.
    • Forgetting .reverse. The merged list would come out in descending order.
    • Forgetting to enqueue the successor. Only the heads would be merged, and the rest of each list would be lost.
    • Duplicate values. Equal values (the two 1s and two 4s in the example) are fine. The queue gives back either one first, and the output is the same.
    • Negative values. The ordering compares Ints, so values such as -3 sort correctly. [[-3,-1],[],[-2]] gives [-3,-2,-1].
    • Returning dummy. That would add the placeholder node at the front.

    Testing

    • [[1,4,5],[1,3,4],[2,6]] gives [1,1,2,3,4,4,5,6].
    • [] gives the empty list.
    • [[]] gives the empty list.
    • [[-3,-1],[],[-2]] gives [-3,-2,-1].
    • A single list such as [[1,2]] comes back as an equal list made of new nodes.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free