# 23. Merge K Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Thoughts:

1. Recursively: Divide and Conquer idea: Top down: split K lists into K/2, K/4, ... 2 (or 1), and merge 2 lists, Bottom up:
then merging two bigger lists until merging them all.

2. Iteratively:

1. using Priority Queue, first pushing every listNode in the list, then everytime poping a node from the Priority Queue,

Checking weather it does have next node, if it does, pushing it into the queue; otherwise, do nothing.

2. make_heap: use vector as if it is a heap!

Code1:

``````/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.empty()) return nullptr;
int len = lists.size();
while(len > 1){
for(int i = 0 ; i < len / 2; i++){
lists[i] = merge2Lists(lists[i], lists[len - 1 - i]);
}
len = (len + 1) / 2;
}

return lists.front();
}

ListNode* merge2Lists(ListNode * l1, ListNode * l2){
if(!l1) return l2;
if(!l2) return l1;

if(l1->val < l2->val){
l1->next = merge2Lists(l1->next, l2);
return l1;
}
else{
l2->next = merge2Lists(l1, l2->next);
return l2;
}
}
};
``````

Code 2: using Priority Queue

``````/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
struct compare{
bool operator()(ListNode* l, ListNode* r){
return l->val > r-> val;
}
};

ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*, vector<ListNode*>, compare> pq;
for(auto l : lists){
if(l) pq.push(l);
}
if(pq.empty()) return nullptr;

ListNode* answer = pq.top(); pq.pop();
ListNode* tail = answer;
if(tail->next) pq.push(tail->next);
while(!pq.empty()){
tail->next = pq.top(); pq.pop();
tail = tail->next;
if(tail->next) pq.push(tail->next);
}

}
};
``````

Code 3: using make_heap

``````/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
static bool heapComp (ListNode * l, ListNode* r){
return l-> val > r->val;
}

ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode* curNode = &head;
vector<ListNode*> pq;

for(int i = 0; i < lists.size(); i++){
if(lists[i]) pq.push_back(lists[i]);
}
make_heap(pq.begin(), pq.end(), heapComp);

while(!pq.empty()){
curNode -> next = pq.front();
curNode = curNode -> next;
pop_heap(pq.begin(), pq.end(), heapComp);
pq.pop_back(); // throw out the least? percolate down?
if(curNode -> next){
pq.push_back(curNode->next);
push_heap(pq.begin(),pq.end(),heapComp); // percolate up?
}
}