Start learning free

LESSON 322 OF 442 · LINKED LISTS

Merge K Sorted Lists in Scala: O(n × k) with a Dummy Node

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

    SCALA · LINKED LISTS

    Merge K Sorted Lists in Scala, explained

    Problem overview

    The method mergeKLists(lists: Array[ListNode]): ListNode receives an array of k linked lists. Each list is sorted in ascending order. It must return one linked list that holds all the values, also in ascending order.

    For lists = [[1,4,5],[1,3,4],[2,6]] the lists are 1->4->5, 1->3->4 and 2->6, and the merged list is 1->1->2->3->4->4->5->6. If the array is empty, or holds only empty lists, the result is an empty list. A list that is empty is a null reference, which is why the code tests lists(i) != null.

    The constraints allow up to 10,000 lists and 10,000 nodes in total. The lesson asks for O(n × k) time, where n is the total number of nodes, and O(1) extra space beyond the list it returns. A faster approach with a min-heap has its own lesson.

    Approach: always take the smallest head

    Because each list is sorted, its smallest remaining value is its head. The smallest remaining value overall is therefore one of the k heads. That suggests a simple loop: look at all the heads, pick the smallest, append its value to the output, and advance that list by one node. Repeat until every list is used up.

    On the example, the heads are 1, 1 and 2. The first 1 goes to the output, and the first list now starts at 4. The heads are 4, 1, 2, so the next pick is the 1 of the second list. The outputs continue 2, 3, 4, 4, 5, 6 in the same manner.

    Each output node costs one scan of k heads, and there are n output nodes, so the time is O(n × k). A min-heap would find the smallest head in O(log k) instead of O(k). This lesson keeps the plain scan because there is no extra structure to build.

    The output list is built with a dummy node. Instead of treating "the first node" as a special case, the code creates a placeholder node, keeps a tail that points to the last node appended, and attaches every new node to tail.next. At the end, the real list begins at dummy.next.

    Step by step

    1. Create the dummy node. ListNode() builds a node with default fields. Its value is never used, and its next will become the head of the merged list.
    2. Start a tail walker. var tail = dummy always points at the last node of the output so far.
    3. Loop while any list has nodes. The condition anyNonNull(lists) is a helper defined later. It is true until every entry of the array is null.
    4. Remember the best list. var ind = -1 holds the index of the list with the smallest head. -1 means no candidate yet.
    5. Scan all the lists with a counted loop over 0 until lists.length.
    6. Update the candidate. If lists(i) is not null, and either no candidate exists or its head is strictly smaller than the best head so far, set ind = i.
    7. Append a new node. tail.next = ListNode(lists(ind).`val`) creates a node with the smallest value and links it after the tail.
    8. Advance the chosen list. lists(ind) = lists(ind).next drops the consumed head from that list. This changes the array, not the nodes.
    9. Move the tail. tail = tail.next now points to the node just appended.
    10. Return dummy.next. It is the last expression of the method, so it is the return value. The method has no return keyword.
    11. Write the helper. anyNonNull takes the array and loops over it with l. If it meets an entry that isn't null, it returns true immediately. After the loop, every entry was null, and the helper's last expression, false, is its result.

    The solution in Scala

    class Solution {
    def mergeKLists(lists: Array[ListNode]): ListNode = {
        val dummy = ListNode()
        var tail = dummy
        while (anyNonNull(lists)) {
            var ind = -1
            for (i <- 0 until lists.length) {
                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
        }
        dummy.next
    }

    def anyNonNull(lists: Array[ListNode]): Boolean = {
        for (l <- lists) {
            if (l != null) {
                return true
            }
        }
        false
    }
}

    The Scala details worth a closer look:

    • Backticks around val. val is a keyword in Scala, and the node's field is named val. Writing it in backticks, `val`, lets you use a reserved word as an ordinary name.
    • ListNode() and ListNode(x). Scala 3 lets you create an instance of a class without writing new. The lesson's ListNode can be created with no arguments, as for the dummy node, or with just a value, as for the other nodes.
    • Last expression as the result. In mergeKLists, the bare dummy.next at the end is the value of the method. In anyNonNull, the final false works the same way. The return true inside the for loop is different: it leaves the whole method from inside a loop body, and Scala 3.5 accepts it with a warning that non-local returns are no longer supported.
    • Arrays are mutable. lists(ind) = lists(ind).next overwrites an entry of the input array. The caller's array is therefore consumed by the call. The linked nodes themselves are never modified, because the output is made of new nodes.
    • Comparing with null. lists(i) != null is the idiomatic way to test for an empty list here. Scala code normally prefers Option, but this lesson's ListNode uses null for "no node".
    • var versus val. dummy never changes, so it is a val. tail and ind are reassigned, so they are var. Reassigning tail doesn't change the node it pointed to before.

    Complexity

    Time: O(n × k). The outer loop runs once per output node, so n times. Each pass scans k heads, and anyNonNull also looks at up to k entries, so a pass costs O(k). With 10,000 lists of one node each, the work is on the order of 100 million simple steps.

    Space: O(1) extra. Apart from the n nodes of the result, which any answer needs, the method keeps the dummy node, tail, ind and the loop counters.

    Edge cases and common mistakes

    • No lists. With lists = [], anyNonNull is false at once, the loop never runs, and dummy.next is null: the empty list.
    • Only empty lists. lists = [[]] is an array holding a null, so the result is again an empty list.
    • Some lists empty. The scan skips null entries, so [null, 1->2] merges to 1->2. Reading lists(i).`val` on a null entry would throw a NullPointerException, which is why the null test comes first in the && chain.
    • The first candidate. When ind is -1, lists(ind) would be an out-of-range index. The condition ind == -1 || short-circuits, so the comparison with lists(ind) is only evaluated when ind is valid.
    • Equal values. With the strict < the first list with the smallest head wins ties. Either choice gives the same values in the output.
    • Negative values. Values may be negative, so don't use 0 as "no candidate" in place of the index -1.
    • Forgetting to advance the list. Without lists(ind) = lists(ind).next, the same head is picked forever and the loop never ends.

    Testing

    • [[1,4,5],[1,3,4],[2,6]] gives [1,1,2,3,4,4,5,6].
    • [] gives [].
    • [[]] gives [].
    • [[], [-3, 2]] gives [-3, 2].
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free