# Clean C++ O(n^2) / O(nlogn) solutions

• Solution 1

O(n^2), 239ms, using solution from 21. Merge Two Sorted Lists.

``````    ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.size() == 0) return NULL;
for(int i = 0, j = 1; j < lists.size(); i++, j++)
lists[j] = mergeTwoLists(lists[i], lists[j]);
return *(lists.end()-1);
}

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(!l1 || !l2) return l1 ? l1 : l2;
while(l1 && l2){
if(l1->val < l2->val){
cur->next = l1;
l1 = l1->next;
}
else{
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
cur->next = l1 ? l1 : l2;
}
``````

Solution 2

O(nlogn), 25ms, beats 97.24%.

``````    ListNode* mergeKLists(vector<ListNode*>& lists) {
auto comp = [](int a, int b){ return a > b;};
priority_queue<int, vector<int>, decltype(comp)>pq(comp);
for(auto x: lists)
while(x) pq.push(x->val), x = x->next;
while(!pq.empty()){
ListNode* node = new ListNode(pq.top());
cur->next = node;
cur = cur->next;
pq.pop();
}
}
``````

Or just store the ListNode* in priority_queue.

``````class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
auto comp = [](ListNode* a, ListNode* b){ return a->val > b->val;};
priority_queue<ListNode*, vector<ListNode*>, decltype(comp)>pq(comp);
for(auto x: lists)
while(x) pq.push(x), x = x->next;