Start learning free

LESSON 318 OF 438 · LINKED LISTS

Merge K Sorted Lists in JavaScript: O(n × k) Brute Force Scan

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 10
    Ctrl + Enter to check

    JAVASCRIPT · LINKED LISTS

    Merge K Sorted Lists in JavaScript, explained

    Problem overview

    The method mergeKLists(lists) receives an array of k sorted linked lists. Each entry of lists is the head node of one list, or null when that list is empty. The method merges all of them into one sorted linked list and returns its head.

    For lists = [[1,4,5],[1,3,4],[2,6]], the three lists are 1->4->5, 1->3->4 and 2->6, and the merged list is 1->1->2->3->4->4->5->6. For lists = [] and for lists = [[]] the answer is an empty list, which is null. There are up to 10,000 lists, each sorted in ascending order, and at most 10,000 nodes in total.

    The lesson asks for O(n × k) time and O(1) extra space, where n is the total number of nodes and k is the number of lists. A faster solution with a min-heap has its own lesson.

    Approach: always take the smallest head

    Every input list is sorted, so the smallest value among all the remaining nodes is always the head of one of the lists. The merged list can be built one node at a time: look at the k heads, pick the smallest, move it to the output, and move that list on to its next node. Repeat until every list is empty.

    Each output node costs one scan of the k heads, and there are n output nodes, which gives O(n × k). It is not the fastest approach, because a min-heap finds the smallest head in O(log k) instead of O(k). It is the simplest, because finding a minimum is a plain loop.

    Here is the first example. The heads are 1, 1 and 2. The scan picks the first 1 (a tie keeps the earlier list), so the output starts 1 and the first list's head becomes 4. The heads are now 4, 1 and 2, the scan picks 1 from the second list, the output is 1->1, and so on, until the heads have all been used up.

    Building the output needs a place to start. The first node of the result is special, because there is no previous node to attach it to. A dummy node avoids that case: the code attaches every node after a tail that begins at the dummy, and the real result is dummy.next.

    Step by step

    1. Create a dummy node with const dummy = new ListNode();. It is a placeholder at the front of the output, so the first real node needs no special handling.
    2. Keep a tail pointer with let tail = dummy;. It always points at the last node of the output so far, and new nodes are attached after it.
    3. Loop while some list still has nodes. The condition lists.some(l => l !== null) is true as long as at least one entry is not null. some stops at the first such entry.
    4. Start each round with let ind = -1;. It remembers which list holds the smallest head, and -1 means "none chosen yet".
    5. Scan all the lists with a counted for loop from i = 0 while i < lists.length. This is the brute-force step, and it is where the factor k comes from.
    6. Update the choice. If lists[i] is not empty, and either nothing has been chosen yet or its head value is strictly smaller than the chosen one, set ind = i. The test lists[i] first skips empty lists, which are null.
    7. Append a copy of the smallest node with tail.next = new ListNode(lists[ind].val);.
    8. Advance the chosen list with lists[ind] = lists[ind].next;, so its next node becomes the head to compare in the next round.
    9. Move tail onto the node just appended with tail = tail.next;.
    10. Return dummy.next after the loop. It is the head of the merged list, or null when no list had any nodes.

    The solution in JavaScript

    class Solution {
    mergeKLists(lists) {
        const dummy = new ListNode();
        let tail = dummy;
        while (lists.some(l => l !== null)) {
            let ind = -1;
            for (let i = 0; i < lists.length; i++) {
                if (lists[i] && (ind === -1 || lists[i].val < lists[ind].val)) {
                    ind = i;
                }
            }
            tail.next = new ListNode(lists[ind].val);
            lists[ind] = lists[ind].next;
            tail = tail.next;
        }
        return dummy.next;
    }
}

    Some JavaScript details worth a closer look:

    • ListNode comes from the lesson. The constructor sets val to 0 and next to null when they are not given. new ListNode() is therefore a node with val 0 and next equal to null, and new ListNode(5) has val 5.
    • Short-circuit && and ||. In lists[i] && (ind === -1 || ...), the right side runs only when lists[i] is truthy. A node object is always truthy, even when its val is 0, and null is falsy. When ind === -1 the comparison lists[ind].val is never evaluated, so it doesn't read from index -1.
    • Strict !== against null. The check expects empty lists to be exactly null. A list that ends is null because the constructor sets next to null. An entry that is undefined would pass l !== null and lead to an error on lists[ind].val.
    • The input array is modified. The line lists[ind] = lists[ind].next overwrites the entries of lists, and at the end they are all null. The nodes themselves are not changed, since the output is built from new nodes. A caller that wants to reuse lists afterwards needs to copy it first.
    • "O(1) extra space" excludes the output. The merged list has one new node per value, and that is the result being returned. Apart from it, the method keeps the dummy node and a few variables.

    Complexity

    Time: O(n × k). The method produces n output nodes, one per pass of the while loop. Each pass scans all k entries of lists, and the some call at the top of the loop looks at up to k entries too, so a pass costs O(k). That gives O(n × k) in total.

    Space: O(1) extra. Not counting the nodes of the returned list, the method uses the dummy node, tail, ind and i.

    Edge cases and common mistakes

    • No lists. With lists = [], some returns false at once, the loop never runs, and the method returns dummy.next, which is null.
    • Only empty lists. With lists = [[]], the only entry is null, so the result is again null.
    • Empty lists mixed with others. For [null, 0->0, null] the scan skips the null entries and the result is 0->0. The lists[i] && test is what stops the scan from reading .val of null.
    • Ties. Using < and not <= keeps the earlier list on equal heads. Both choices give a correct sorted result, since equal values are interchangeable.
    • Returning dummy. The dummy node's value of 0 would appear at the front of the answer. The head of the merged list is dummy.next.
    • Forgetting to advance the chosen list. Without lists[ind] = lists[ind].next the same node is picked forever and the loop never ends.
    • Forgetting to move tail. Each new node would overwrite the previous one's next, and the result would hold only the last node.

    Testing

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