# 23 Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
My approach with this problem was to basically create a new linkedlist from scratch. I first grab all the min elements from the list. This will take O(k) time for k lists. Next, I find the minimum element according to that list. This will take O(N) for N minimum elements. That index is returned, and I insert it to the end of a linkedlist. This operation will take O(N) as well for N inserts. Next, I remove the head of the current minimum List. This will allow the next iteration to chose the next minimum element. Remove all will also take O(N) time.
Implementation 1
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
int findMinIndex(vector<int> &mins) {
int min = mins.at(0);
int index = 0;
for (int i = 0; i < mins.size(); i++) {
if (i < min) {
min = mins.at(i);
index = i;
}
}
return index;
}
// empty
ListNode *itr;
// deletions always occurs at head
delete itr;
}
void insert(ListNode *front, ListNode *end, ListNode *thisNode) {
if (front == nullptr) {
front = end = thisNode;
}
end->next = thisNode;
end = thisNode;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
vector<int> mins(lists.size());
ListNode *front, *end;
front = end = nullptr;
bool notEmpty = true;
while (notEmpty) {
// get all min elements given they are not empty
for (int i = 0; i < lists.size() && (!lists.at(i)); i++) {
mins.push_back(lists.at(i)->val);
notEmpty = true;
}
// remove min_index
int min_index = findMinIndex(mins);
insert(front, end, lists.at(min_index));
mins.clear();
mins.resize(0);
notEmpty = false;
}
return front;
}
Implementation 2
The Idea: Maintain a priority queue take keeps track of the minimum elements. Initially push all the front `ListNode*` into the `pq`. Then build a new list that continually takes the top of list `pq` (minimum element). As it does so, the minimum element replaces its position with the adjacent (next) element to it's list (if it's not null).
Time Complexity: O(nlogk) time, and O(K) space. The heap will only maintain k elements (the current minimum from each list). As soon as node is popped from the heap, it either becomes replaced by the next element in the list, or the list is empty, in which case no elements are added. Hence because the heap begins with at most k elements in the list, and at most one element is popped and replaced with a new element in the heap, the space complexity is proportional to the number of lists. For the time complexity, the heap does logk operations (since there are at most k elements in the heap) for all the elements in the lists combined (n).
struct CmpList
{
bool operator()(const ListNode* lhs, const ListNode* rhs) const
{
return lhs->val > rhs->val;
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*, vector<ListNode*>, CmpList> pq;
for (ListNode *lp : lists)
if (lp) pq.push(lp);
ListNode *head = nullptr, *tail = nullptr;
// get started by setting up head
if (!pq.empty()) {
ListNode *front = pq.top(); pq.pop();
if (front->next) pq.push(front->next);
}
while (!pq.empty()) {
ListNode *front = pq.top(); pq.pop();
tail->next = front;
tail = front;
if (front->next) pq.push(front->next);
}
if (tail) tail->next = nullptr;
}
Testing
int main()
{
ListNode* one = new ListNode(1);
ListNode* two = new ListNode(2);
ListNode* three = new ListNode(3);
one->next = two;
two->next = three;
three->next = nullptr;
vector<ListNode*> t1 = { one };
vector<ListNode*> t2 = { nullptr };
}
Python
I aimed for a cleaner implementation here. We begin by iterating through the lists and appending the head nodes as tuple into a heapq. You may nice that our tuple carries an almost unnecessary 2 argument within the tuple. This argument is essentially used to break ties when two lists carry the same value. In our case, it does not matter which element gets added next to our list, but including the index `i` ensures when two lists are compared and they have the same value, a decision can be made in selecting which node to percolate in the heapq tree. In our case, we are arbitrary prioritizing the list that came first.
import heapq
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
Runtime O(nlogn) - where n is the number of elements
Space O(k)
"""
# initialize a dummy node for head start
# it will do some of the work for us
heap = []
# initialize the hq with the head of every list node
# if it not empty hq with maintain smallest value
# of the first tuple element by default
for i in range(0, len(lists)):
if lists[i]: heapq.heappush(heap, (lists[i].val, i, lists[i]))
while heap:
# point head to the next smallest element
root = heapq.heappop(heap)
tail.next = root
# iterate to the next node of the
# linked list we popped from
tail = tail.next
# if that list isnt yet empty, then
# store that next element into the hq
if tail.next:
heapq.heappush(heap, (tail.next.val, root, tail.next))
# return head node which is after dummy node