Start learning free

LESSON 321 OF 441 · LINKED LISTS

Merge K Sorted Lists in C#: O(n × k) by Scanning the Heads

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

    C# · LINKED LISTS

    Merge K Sorted Lists in C#, explained

    Problem overview

    The method MergeKLists receives an array of k linked lists, ListNode[] lists. Each list is sorted in ascending order. It returns one sorted linked list holding all the values. The lesson's ListNode has an int val, a ListNode next and constructors that take no argument or a value.

    For [[1, 4, 5], [1, 3, 4], [2, 6]] the result is 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6. For [] (no lists at all) and for [[]] (one empty list) the result is the empty list, which is null. The array can hold up to 10,000 lists, with at most 10,000 nodes in total.

    Approach: always take the smallest head

    Each input list is sorted, so its smallest unused value is its first node, its head. The smallest unused value overall is therefore the smallest of the k heads. That gives a simple procedure: repeat the following until every list is empty.

    1. Scan the heads of all lists and find the smallest.
    2. Append its value to the output.
    3. Advance that list to its next node.

    With n values in total, the output grows n times, and each time the scan looks at up to k heads: O(n × k) time. The lesson's note asks for exactly this, and says a faster O(n log k) solution with a min-heap has its own lesson.

    Two details make the code clean. A dummy node placed before the real head removes the special case of appending the very first node. A tail variable always points at the last node appended, so appending is tail.next = ....

    On the first example, the heads are 1, 1 and 2. The first list wins the tie, since only a strictly smaller head replaces the current best, so its 1 is appended and its head becomes 4. Next the heads are 4, 1 and 2, the second list's 1 is appended, and so on, until all lists have run out.

    Step by step

    1. Create the sentinel ListNode dummy = new ListNode();. The merged list is dummy.next, and the sentinel's own value is never used.
    2. Create the walker ListNode tail = dummy;.
    3. Loop while any list still has nodes. The loop condition calls a helper, AnyNonNull(lists), written at the end.
    4. Start each round with int ind = -1;. It remembers which list has the smallest head. The value -1 means that none has been picked yet.
    5. Scan all lists with a for loop from 0 to lists.Length - 1.
    6. Update the best choice. If lists[i] is not null and either nothing has been picked yet or its head is strictly smaller than the picked list's head, set ind = i. The null test skips exhausted lists, and it comes first so the .val reads never touch a null.
    7. Append a new node carrying the smallest value: tail.next = new ListNode(lists[ind].val);.
    8. Advance the chosen list: lists[ind] = lists[ind].next;. A list that runs out becomes null.
    9. Move tail forward onto the node just appended.
    10. Return dummy.next, the head of the merged list.
    11. Write the helper AnyNonNull below MergeKLists. It takes the array of lists and answers whether any list still has nodes.
    12. Loop over the array with foreach (ListNode l in lists).
    13. Return true at the first non-null list. One live list is enough to continue.
    14. Return false after the loop. Every entry was null, so the merge is done.

    The solution in C#

    class Solution {
    public ListNode MergeKLists(ListNode[] lists) {
        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        while (AnyNonNull(lists)) {
            int ind = -1;
            for (int i = 0; i < lists.Length; i++) {
                if (lists[i] != null && (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;
    }
    private bool AnyNonNull(ListNode[] lists) {
        foreach (ListNode l in lists) {
            if (l != null) {
                return true;
            }
        }
        return false;
    }
}

    The C# details worth knowing:

    • Short-circuit evaluation. In lists[i] != null && (...), the right side runs only when the left side is true. That is what protects lists[i].val from a null. Inside the parentheses, ind == -1 || ... works the same way: when ind is -1 the comparison with lists[ind] is skipped, since lists[-1] would throw an IndexOutOfRangeException.
    • Linked list nodes are references. ListNode is a class, so lists[ind] = lists[ind].next only moves a reference. The input nodes are never changed.
    • The method does change the lists array. Its entries are advanced as the merge goes, and when the method returns, they are all null. A caller who needs the array afterwards must keep its own copy of the heads.
    • The result is made of new nodes. new ListNode(lists[ind].val) copies each value. The merged list shares no node with the inputs, so changing it doesn't affect them.
    • Empty input. AnyNonNull is false at once, the loop never runs, and dummy.next is still null. That is the right answer for [] and for [[]], where the only entry is null.
    • private helper. The tests call only MergeKLists, so the helper can be private. Both methods belong to the same class and can call each other.

    Complexity

    Let n be the total number of nodes and k the number of lists.

    Time: O(n × k). The while loop runs once per node, so n times. Each round scans k heads, and AnyNonNull looks at up to k entries, so a round costs O(k). With the largest allowed inputs, this is on the order of 100 million simple steps.

    Space: O(1) extra. Besides the returned list, which has one new node per value, the method keeps the dummy node and a few variables.

    Edge cases and common mistakes

    • No lists. [] returns null.
    • Only empty lists. [[]] returns null, and so does an array of several empty lists. The same goes for entries that are null.
    • Some lists empty. [[], [7]] returns the one-node list 7. The null test skips the empty list in every scan.
    • Equal heads. With [1, 4, 5] and [1, 3, 4], either 1 can go first, and the result is the same. Because the comparison is strictly less than, the earlier list wins ties.
    • Negative values. [[-5, -5], [-5]] returns -5 -> -5 -> -5. The comparison needs no special case.
    • Testing val before null. Reading lists[i].val on an exhausted list throws NullReferenceException.
    • Forgetting to advance the chosen list. The same node would be picked forever, and the loop never ends.
    • Returning dummy instead of dummy.next. The sentinel would appear as an extra 0 at the front of the list.

    Testing

    • [[1, 4, 5], [1, 3, 4], [2, 6]] gives [1, 1, 2, 3, 4, 4, 5, 6].
    • [] gives [].
    • [[]] gives [].
    • [[], [7]] gives [7].
    • [[-5, -5], [], [-5]] gives [-5, -5, -5].
    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