Merge K Sorted Lists Problem

Given k singly linked lists where each linked list is sorted in ascending order, merge all of them into a single sorted linked list.

Example:

Input: [ [1 -> 3 -> 5], [3 -> 4], [7] ].

Output: 1 -> 3 -> 3 -> 4 -> 5 -> 7

Notes:

Constraints:

• 0 <= k <= 104.
• 0 <= Length of each linked list <= 103.
• -109 <= Node values <= 109.
• Sum of the lengths of all linked lists won’t exceed 105.

Solutions

We provided three solutions.

Throughout this editorial, we will refer to the input array of the linked lists as lists, its size as k and the total number of nodes in all the given linked lists as n.

We will start with a brute force approach and will then discuss the areas of optimization to reach the optimal solutions.

1) brute_force_solution.cpp

All the individual lists are sorted. Therefore, a brute force is to compare the heads of all the linked lists one by one and choose the linked list whose head has the minimum value.

The head of the selected linked list will then be appended at the end of the final linked list which will initially be empty.

After this, we will advance the head node of the selected list to point to its next node.

The same procedure is continued till no node is left to be added in the final linked list, ie, when the heads of all the given lists point to a NULL node.

Time Complexity:

O(k * n).

In total, there are n nodes to be added in the final list and it will take an entire traversal of k heads on average to find the node with the minimum value.

Auxiliary Space Used:

O(1).

We used only a constant amount of extra space.

Space Complexity:

O(n + k).

Space used for input: O(n + k).

Auxiliary space used: O(1).

Space used for output: O(n).

So, the total space complexity: O(n + k).

// -------- START --------

/*
    class SinglyLinkedListNode {
        public:
            int data;
            SinglyLinkedListNode *next;
            SinglyLinkedListNode(int node_data) {
                this->data = node_data;
                this->next = nullptr;
            }
    };
*/
SinglyLinkedListNode * merge_k_lists(vector < SinglyLinkedListNode * > lists) {
    SinglyLinkedListNode * head = NULL;
    SinglyLinkedListNode * tail = NULL;

    int min_index;
    while (1) {
        min_index = 1e9 + 1;

        // Finding the list index with the minimum value of head node.
        for (int i = 0; i < lists.size(); i++) {            if (lists[i] != NULL) {                if (min_index == 1e9 + 1 or lists[i] -> data < lists[min_index] -> data) {
                    min_index = i;
                }
            }
        }
        if (min_index == 1e9 + 1) {
            break;
        }

        if (head == NULL) {
            head = lists[min_index];
            tail = lists[min_index];
        } else {
            tail -> next = lists[min_index];
            tail = tail -> next;
        }
        lists[min_index] = lists[min_index] -> next;
        tail -> next = NULL;
    }
    return head;
}

// -------- END --------

2) min_head_solution.cpp

In the above solution, we did a linear traversal of k heads to find the node with the minimum value.

This traversal can be avoided and the same work can be done more time efficiently using some extra amount of space.

We can store the heads of all the k lists in a min-heap that arranges the nodes on the basis of their values. Now, using this min-heap, we can find the head with the minimum value in O(log(k)) time.

After adding all the non-NULL heads in the min-heap, we will have to follow the following steps:

• Pop out the node with the minimum value, let us call this node selected_head.
• Extend the final list using the selected_head.
• If selected_head->next is non-NULL, then add the selected_head->next in the min-heap as this is the new head of the selected list.

We will perform the above steps till the min-heap is non-empty.

Time Complexity:

O(n * log(k)).

We have n nodes to add and searching for the node with the minimum value in the min-heap will take an O(log(k)) time on an average.

So, since we also have n nodes to pop-out from the min-heap, it would take O(n * log(k)) time in total.

Auxiliary Space Used:

O(k).

At any point in time, the min-heap will have a maximum size of k.

Space Complexity:

Space used for input: O(n + k).

Auxiliary space used: O(k).

Space used for output: O(n).

So, total space complexity: O(n + k).

// -------- START --------

/*
    class SinglyLinkedListNode {
        public:
            int data;
            SinglyLinkedListNode *next;
            SinglyLinkedListNode(int node_data) {
                this->data = node_data;
                this->next = nullptr;
            }
    };
*/
SinglyLinkedListNode * merge_k_lists(vector < SinglyLinkedListNode * > lists) {
    SinglyLinkedListNode * head = NULL;
    SinglyLinkedListNode * tail = NULL;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    for (int i = 0; i < lists.size(); i++)    {        if (lists[i] != NULL)        {            pq.push({lists[i]->data, i});
        }
    }

    int min_index;
    while (!pq.empty()) {
        min_index = pq.top().second;
        pq.pop();

        if (head == NULL) {
            head = lists[min_index];
            tail = lists[min_index];
        }
        else {
            tail->next = lists[min_index];
            tail = tail->next;
        }
        lists[min_index] = lists[min_index]->next;
        tail->next = NULL;

        if (lists[min_index] != NULL)
        {
            pq.push({lists[min_index]->data, min_index});
        }
    }
    return head;
}

// -------- END --------
</pair<int,></pair<int,></pair<int,>

3) divide_and_conquer_solution.cpp

Note that we can merge k sorted linked lists by merging two lists, k – 1 number of times. We can initially merge the first two linked lists, the resultant list can be merged with the third linked list and so on. Doing this, we will finally have a single sorted linked list having all the nodes of the input lists. This process will take O(n * k) amount of time as each process of merging two lists will take O(n) time in the worst case.

As we keep merging more and more linked lists into the final list, the size of the final list keeps increasing. Therefore, we will be traversing each node in the linked list more than once.

The nodes of the first two linked lists will be involved in all the merge processes, hence they will be traversed a maximum of k – 1 number of times. Similarly, the nodes of the third list will be involved in k – 2 merge processes, hence they will be traversed a maximum of k – 2 number of times and so on.

We can reduce the number of times each node is traversed if we can somehow reduce the sizes of the subsequent lists which help us reach the final list. The size of the intermediate lists can be reduced using a divide and conquer process:

• Instead of merging each list into the final list, we will pair up the given k lists and merge each pair.
• After the first cycle of pairing, we will be left with k/2 number of lists. We will follow a similar process and pair up the k/2 lists and merge each pair.
• We will then be left with k/4 number of pairs and a similar process continues.

We will continue this till we are finally left with a single linked list.

The complete process will look like the following if we initially have k = 4 number of linked lists.

Note that,

• We are first merging the list_0 and the list_3 and storing the result in list_0. Similarly, the merged result of list_1 and list_2 is stored in list_1.
• In the second step, we merge the list_0 and the list_1 and store the result in list_0. Now, we are left with just a single linked list. Therefore, we stop and return list_0.

In each level, we merge the first list from the beginning with the first list from the end, second list from the beginning with the second list from the end and so on. Any other way of pairing would also produce the same output.

Also note that, we traverse all of the n nodes at most once in each level and the number of such levels is equal to log(k). Therefore, each node is now traversed a maximum of log(k) number of times.

Time Complexity:

O(n * log(k)).

During each level of pairing and merging, we are traversing each of the n nodes at most once and the number of such levels is equal to log(k).

Auxiliary space used:

O(1).

We used only a constant amount of extra space.

Space Complexity:

Space used for input: O(n + k).

Auxiliary space used: O(1).

Space used for output: O(n).

So, total space complexity: O(n + k).

// -------- START --------

/*
    class SinglyLinkedListNode {
        public:
            int data;
            SinglyLinkedListNode *next;
            SinglyLinkedListNode(int node_data) {
                this->data = node_data;
                this->next = nullptr;
            }
    };
*/
SinglyLinkedListNode * merge_2_lists(SinglyLinkedListNode * head1, SinglyLinkedListNode * head2) {
    if (head1 == NULL) {
        return head2;
    }
    if (head2 == NULL) {
        return head1;
    }

    // Using a dummy node to merge two linked lists. All the nodes, including the head will be
    // inserted after this dummy node.
    SinglyLinkedListNode * dummy = new SinglyLinkedListNode(0);
    SinglyLinkedListNode * tail = dummy;

    while (head1 != NULL or head2 != NULL) {
        if (head1 == NULL) {
            tail -> next = head2;
            head2 = head2 -> next;
        } else if (head2 == NULL) {
            tail -> next = head1;
            head1 = head1 -> next;
        } else {
            if (head1 -> data < head2 -> data) {
                tail -> next = head1;
                head1 = head1 -> next;
            } else {
                tail -> next = head2;
                head2 = head2 -> next;
            }
        }
        tail = tail -> next;
    }

    // head of the merged linked list is dummy->next.
    return dummy -> next;
}

SinglyLinkedListNode * merge_k_lists(vector < SinglyLinkedListNode * > lists) {
    if (lists.size() == 0) {
        return NULL;
    }

    int low, high, last = lists.size() - 1;

    // We will continue until we are left with only a single linked list.
    while (last != 0) {
        low = 0;
        high = last;
        while (low < high) {
            lists[low] = merge_2_lists(lists[low], lists[high]);
            low++;
            high--;
        }

        last = high;
    }
    return lists[0];
}

// -------- END --------