Start learning free

LESSON 322 OF 442 · LINKED LISTS

Merge K Sorted Lists in TypeScript: 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 <= 10⁴
0 <= lists[i].length <= 500
-10⁴ <= lists[i][j] <= 10⁷
lists[i] is sorted in ascending order.
The sum of lists[i].length will not exceed 10⁴.

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

Guided

Ctrl + Enter to check

TYPESCRIPT · LINKED LISTS

Merge K Sorted Lists in TypeScript, explained

Problem overview

The method mergeKLists receives an array lists of k sorted linked lists. Each list is given by its head node, and an empty list is null. It returns one sorted linked list containing every value from all the lists.

For three lists 1→4→5, 1→3→4 and 2→6, the result is 1→1→2→3→4→4→5→6. An empty array of lists gives an empty result, and so does an array holding one empty list; in both cases the method returns null.

This lesson asks for O(n × k) time and no extra space beyond the merged list, where n is the total number of nodes and k the number of lists. A min-heap version that runs in O(n log k) has its own lesson.

Approach: always take the smallest head

Every input list is already sorted, so the smallest value not yet used is always the first node of one of the lists. Merging is therefore a repeated choice: look at the current head of every list, take the smallest, add its value to the result, and advance that list by one node. Repeat until every list is empty.

Finding the smallest head is a plain scan over the k heads, which costs O(k). It runs once for each of the n output nodes, so the total is O(n × k). That is the brute-force way to pick the minimum, and its weakness is the repeated scan: a min-heap finds the smallest head in O(log k) instead.

For the result, a dummy node placed before the real head avoids a special case. Without it, the code that appends the first node would differ from the code that appends the others. With it, every append is tail.next = ... and the answer is dummy.next.

On the example, the heads are 1, 1 and 2. The scan uses a strict <, so the first of the two equal 1s wins: its value is appended and that list advances to 4. The heads are now 4, 1 and 2, then 4, 3 and 2, and so on, until the lists run out in the order 1, 1, 2, 3, 4, 4, 5, 6.

Step by step

Create the dummy node dummy with new ListNode(). Its own value is never used. The merged list will hang off dummy.next.
Declare tail as a variable that always points at the last node appended. It starts at the dummy.
Loop while some list still has nodes. lists.some(l => l !== null) is true as long as at least one entry is not null.
Declare ind as -1. It remembers which list has the smallest head, and -1 means "no choice yet".
Scan all k lists with an indexed loop over lists.
Update ind when a list wins. A list competes if its entry is not null. It wins if nobody has been picked yet or its head value is strictly smaller than the current best.
Append a new node with the winning value: tail.next = new ListNode(lists[ind].val).
Advance the winning list past the node just used: lists[ind] = lists[ind].next. When a list runs out, its entry becomes null and it stops competing.
Move tail onto the node just appended.
Return dummy.next after the loop. It is null when no values were appended.

The solution in TypeScript

class Solution {
    mergeKLists(lists: Array<ListNode | null>): ListNode | null {
        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;
    }
}

The TypeScript details worth a closer look:

The union type ListNode | null. An empty list is null, so each entry of lists is either a node or null. With the lesson's compiler settings, reading .val from such an entry isn't reported as an error. The lists[i] && ... guard is what keeps the code from reading a property of null at run time.
Truthiness as a null check. lists[i] && (...) is false for null, so exhausted lists are skipped. The && also short-circuits: the right side is not evaluated when the left side is falsy.
Array.prototype.some. It calls the arrow function on each entry and stops at the first true, so the check is cheap while the first list is still non-empty, and costs up to k once the leading lists are empty.
The input array is consumed. lists[ind] = lists[ind].next overwrites entries of the caller's array. When the method returns, every entry is null. The nodes themselves are not changed, because the result is built from new nodes, so the original lists stay intact for anyone who kept a reference to their heads.
const and mutation. const dummy only fixes the variable. Its next field is still assigned later. tail is let because it is reassigned.

Complexity

Time: O(n × k). The outer loop runs once per output node, so n times. Each run does one some check and one scan, both up to k steps. With the constraints' limit of 10^4 nodes in total and up to 10^4 lists, the worst case is on the order of 10^8 simple steps, which is why the heap version is worth learning.

Space: O(1) extra. Besides the merged list, which has one new node per value and is the required output, the method holds the dummy node, tail, ind and i.

Edge cases and common mistakes

No lists. lists = []: some on an empty array is false, the loop never runs and the method returns dummy.next, which is null.
Only empty lists. [null] or [null, null] behave the same way.
Some lists empty. [null, 1→2] works: the null entry never competes, and the result is 1→2.
Equal values. The strict < keeps the first of equal heads, and the result is the same sorted sequence either way.
Using ind without the -1 check. Starting with a value such as 0 would treat the list at index 0 as already chosen, even when it is empty.
Returning dummy. That would put a bogus extra node at the front. The answer starts at dummy.next.
Forgetting to move tail. Every new node would overwrite the previous one's place, and the result would hold only the last value.

Testing

[1→4→5, 1→3→4, 2→6] gives 1→1→2→3→4→4→5→6.
[] gives an empty list (null).
[null] gives an empty list (null).
[null, -3→2] gives -3→2.
[1→1, 1] gives 1→1→1.

Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free