Start learning free

LESSON 317 OF 437 · LINKED LISTS

Merge K Sorted Lists in C++: O(n × k) with a Scan of the Heads

Practice O(n × k) Read the full explanation

You are given a vector 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 14

Guided

Ctrl + Enter to check

C++ · LINKED LISTS

Merge K Sorted Lists in C++, explained

Problem overview

The function mergeKLists receives a vector lists of k singly linked lists, each sorted in ascending order. It must return the head of one sorted list that holds every value from all of them. The vector can be empty, and any entry can be a null pointer, which stands for an empty list.

With lists = [[1,4,5],[1,3,4],[2,6]] the answer is 1->1->2->3->4->4->5->6. For [] and for [[]] the answer is the empty list, a null pointer.

The statement allows O(n × k) time, where n is the total number of nodes and k the number of lists, and O(1) extra space beyond the list that is returned.

Approach: always take the smallest head

Each input list is already sorted, so the smallest value not yet used is always at the front of one of the lists. Picking it takes one pass over the k heads. Append it to the output, move that input list forward by one node, and repeat until every list is empty.

Every output node costs one scan of k heads, and there are n output nodes, which gives O(n × k). It is the simplest correct method and it needs no extra data structure. A min-heap of heads brings the cost per node down to O(log k); that faster version has its own lesson.

On the example, the three heads are 1, 1 and 2. The first scan picks the first list (a tie keeps the earlier list, because the comparison is strict), then its head becomes 4. The heads are now 4, 1 and 2, so the next pick is 1 from the second list, then 2, and so on until the output reads 1, 1, 2, 3, 4, 4, 5, 6.

Step by step

Create a dummy node. The merged list is built after it, and dummy->next is the result. Without it, the first appended node would need special handling.
Keep a tail pointer that always points at the last node of the merged list, starting at the dummy.
Loop while some list still has nodes. A helper, anyNonNull, answers that question and is written last.
Remember the best list. ind starts at -1, meaning that no list has been chosen yet.
Scan all the lists with an index loop over the vector.
Update the choice. A list is a candidate only if its pointer is not null. It wins if nothing has been chosen yet or if its head value is strictly smaller than the current best.
Append a new node that carries the chosen value after tail.
Advance the chosen input list by setting lists[ind] to its next.
Move tail onto the node just appended.
Return dummy->next after the loop.
Write the helper. It walks over the vector and returns true at the first non-null pointer, and false if it reaches the end.

The solution in C++

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* dummy = new ListNode();
        ListNode* tail = dummy;
        while (anyNonNull(lists)) {
            int ind = -1;
            for (int i = 0; i < (int)lists.size(); 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;
    }

    bool anyNonNull(vector<ListNode*>& lists) {
        for (auto* l : lists) {
            if (l) {
                return true;
            }
        }
        return false;
    }
};

The C++ details worth a closer look:

The cast in the loop. lists.size() is unsigned. Casting it to int keeps the comparison i < (int)lists.size() between two signed numbers, so the compiler has no signed/unsigned mismatch to warn about.
Pointers as conditions. lists[i] && ... is true when the pointer is not null, and the right-hand side only runs in that case. That order matters: lists[i]->val on a null pointer is undefined behaviour. The same short-circuit protects lists[ind]->val, because ind == -1 is checked first.
The vector is modified. The parameter is a reference, and lists[ind] = lists[ind]->next moves the caller's pointers. After the call, every entry of lists is null. The original nodes are not changed or freed, because the result is made of new nodes.
New nodes, not relinking. new ListNode(value) copies each value into a fresh node, so the merged list is separate from the inputs. The dummy node is allocated with new and never deleted; a long-running program would free it, or use a stack-allocated dummy such as ListNode dummy;.
The helper's loop. for (auto* l : lists) copies one pointer at a time, which is cheap. The vector itself is passed by reference, so the helper doesn't copy it.
Calling a member from a member. anyNonNull is defined after mergeKLists but inside the class, and member functions can use each other regardless of order.

Complexity

Time: O(n × k). The outer loop runs once per output node, so n times. Each pass calls anyNonNull, which stops at the first non-null entry but can look at all k entries when the non-null ones are at the end, and then scans all k heads. Both are O(k) per pass.

Space: O(1) extra. Beyond the n nodes of the returned list, the code keeps the dummy, tail and a few integers. It never copies the vector.

Edge cases and common mistakes

No lists. With an empty vector, anyNonNull is false at once and the function returns dummy->next, which is null.
Only empty lists. [[]] is a vector holding one null pointer. The result is again null.
Some lists empty. [[1,1], null, [1]] gives 1->1->1. Null entries are skipped in the scan.
Dereferencing a null head. Comparing lists[i]->val without the null check crashes as soon as one list runs out.
Starting ind at 0. List 0 may be empty, so the first comparison would read a null pointer. The value -1 together with the explicit check avoids that.
Using <=. It still produces a sorted list, but ties then favour the later list. The strict comparison keeps equal values in the order of their lists.
Forgetting to advance the input. Without lists[ind] = lists[ind]->next, the same value 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 [].
[[1,1], [], [1]] gives [1,1,1].

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

Start learning free