LeetCode #23

# Description:

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

## Example:

``````Note
``````

# Idea:

1. 典型的merge sort思想。

Time: O(nklogk)

1. 也可以用min heap来搞，创建一个heap，k size，每个list push进第一元素，然后heap pop，对应的list再进一个（如果not empty），指导heap为空。

Time: O(nklogk)

# Code:

Divide and Conquer

``````class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.empty()) return NULL;

int n=lists.size();
mergeDivide(lists, 0, n-1);

return lists[0];
}

// 就是merge sort
void mergeDivide(vector<ListNode*>& lists, int left, int right){
if(left < right){
int mid=left+(right-left)/2;
mergeDivide(lists, left, mid);
mergeDivide(lists, mid+1, right);
lists[left]=mergeTwoLists(lists[left], lists[mid+1]);
}
}

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1==NULL || l2==NULL) return l1==NULL? l2 : l1;
ListNode dummy(-1);

ListNode * curr = &dummy;
while(l1!=NULL && l2!=NULL){
if(l1->val<=l2->val){
curr->next=l1;
l1=l1->next;
}
else{
curr->next=l2;
l2=l2->next;
}
curr=curr->next;
}

curr->next = l1==NULL? l2: l1;

return dummy.next;
}
};
``````