The first solution has good space complexity equal O( number of lists ).

The second solution has worst space complexity O( number of elements) but is faster(388ms) because it uses the std::vector to sort the elements.

//

// First solution

//

```
ListNode* mergeKLists(vector<ListNode*>& lists)
{
auto comp = [] ( ListNode* y, ListNode* x) { return !x || y && x->val < y->val; };
priority_queue<ListNode*, vector<ListNode*>, decltype(comp)> queue( comp , lists );
ListNode dummy(0);
ListNode* node = &dummy;
while (! queue.empty())
{
ListNode* smallest = queue.top();
queue.pop();
node->next = smallest;
if (smallest)
{
node = smallest;
queue.push(smallest->next);
}
}
return dummy.next;
}
```

//

// Second solution

//

```
ListNode* mergeKLists(vector<ListNode*>& lists)
{
vector<ListNode*> v;
for (auto list : lists)
{
while (list)
{
v.push_back(list);
list = list->next;
}
}
sort( v.begin(), v.end(), [] ( ListNode* x, ListNode* y) { return !x || y && x->val < y->val;} );
ListNode dummy(0);
ListNode* node = &dummy;
for ( auto next : v )
{
node->next = next;
node = node->next;
}
node->next = 0;
return dummy.next;
}
```