# [leetcode] Merge k Sorted Lists

### Merge k Sorted Lists

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

Tag: divide and conquer, linked list, heap

update 9/22/2015

Merge sort the k lists. O(knlogk) in time, O(1)

```//merge these
/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.size() == 0) return NULL;
return _mergeKLists(lists, 0, lists.size());
}

//not include end, include start
ListNode * _mergeKLists(vector<ListNode*>& lists, int start, int end){
//base case
if(end - start == 1){
return lists[start];
}
int mid = start + (end - start) / 2;
ListNode * l1 = _mergeKLists(lists, start, mid);
ListNode * l2 = _mergeKLists(lists, mid, end);

ListNode dummyNode = ListNode(0);
ListNode *tail = &dummyNode;
while(l1 != NULL && l2 != NULL){
ListNode*& p = l1->val < l2->val ? l1: l2;
tail->next = p;
tail = tail->next;
p = p->next;
}
tail->next = l1 == NULL? l2: l1;
return dummyNode.next;
}
};```

[{7},{49},{73},{58},{30},{72},{44},{78},{23},{9},{40},{65},{92},{42},{87},{3….大约有几千个。

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
ListNode * tail = NULL;
ListNode * p = NULL;
vector<ListNode *>::iterator it,idx;
//lists is empty
if (lists.empty()){
return NULL;
}

//some listnode are empty
if (lists.size() > 0){
for(it = lists.begin(); it != lists.end(); it++){
if (*it == NULL){
lists.erase(it);
it--; // this is important, since iterator should be decreased after erase operation
}
}
}

while(lists.size() > 0){
int min = lists[0]->val;
idx = lists.begin();
for(it = lists.begin() + 1; it != lists.end(); it++){
if ((*it)->val < min){
min = (*it)->val;
idx = it;
}
}

}
else{
tail->next = *idx;
tail = *idx;
}
if ((*idx)->next == NULL){
lists.erase(idx);
}
else{
*idx = (*idx)->next;
}

}
}
};```

1.20更新：

C++代码：

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class cmp
{
public:
bool operator()(const ListNode * p1, const ListNode * p2) const{
if (p1->val <= p2->val){
return false;
}

else{
return true;
}
}
};
class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
vector<ListNode *>::iterator it;

ListNode * tail = NULL;
ListNode * p = NULL;
//lists is empty
if (lists.empty()){
return NULL;
}

//some elements in lists are empty
for(it = lists.begin(); it != lists.end(); it++){
if (*it == NULL){
lists.erase(it);
it--;
}
}

if(lists.empty()){
return NULL;
}

priority_queue<ListNode *, vector<ListNode *>, cmp>pq(cmp(), lists);

//handle the first element
p = pq.top();
pq.pop();
p = p->next;
if (p != NULL){
pq.push(p);
}

//loop all the elements
while(!pq.empty()){
p = pq.top();
pq.pop();

tail->next = p;
tail = tail->next;

p = p->next;
if(p != NULL){
pq.push(p);
}
}

tail->next = NULL;