An easy to understand solution in C++. Complexity proportional to O(k*l), where *k* = number of lists, and *l* = length of the largest list. No extra space used.

```
class Solution {
private:
struct key_t{
int val;
int idx;
key_t() : val(0), idx(0) {}
};
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.size() == 0) return NULL;
ListNode* merger = 0;
ListNode* front = 0;
key_t key;
key.val = INT_MAX;
while(true) {
for (int i = 0; i < lists.size(); ++i) {
if(lists[i] == NULL) { // reached the end?
continue;
}
if(lists[i]->val < key.val) {
key.val = lists[i]->val;
key.idx = i;
}
}
if(key.val == INT_MAX) { // done?
break;
}
// add a new node with min found
if(merger == NULL) {
merger = new ListNode(key.val);
front = merger;
} else {
merger->next = new ListNode(key.val);
merger = merger->next;
}
// advance the list[i] pointer
lists[key.idx] = lists[key.idx]->next;
// reset
key.val = INT_MAX;
}
return front;
}
};
```