image.png
https://algorithm.yuanbin.me/zh-hans/linked_list/merge_k_sorted_lists.html
解法一，选择归并
/**
* 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 NULL;
ListNode * dummy = new ListNode(INT_MAX);
ListNode * lastnode = dummy;
while(true){
int count = 0;
int index = -1, tmp = INT_MAX;
int i;
for( i = 0; i < lists.size(); i++){
if(lists[i] == NULL){
count++;
if(count == lists.size()){
lastnode->next = NULL;
return dummy->next;
}
continue;
}
if(lists[i] != NULL && lists[i]->val < tmp){
index = i;
tmp = lists[i]->val;
}
}
lastnode->next = lists[index];
lastnode = lastnode->next;
lists[index] = lists[index]->next;
}
}
};
解法二：两个的合并，小的逐渐并入！！！要注意合并两个链表的模板
/**
* 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 NULL;
ListNode * head = lists[0];
for(int i = 1; i < lists.size();i++){
head = merge(head, lists[i]);
}
return head;
}
private:
ListNode* merge(ListNode * left, ListNode * right){
ListNode * dummy = new ListNode(0);
ListNode * p = dummy;
while(left && right){
if(left->val < right->val){
p->next = left;
p = p->next;
left = left->next;
}
else{
p->next = right;
p = p->next;
right = right->next;
}
}
p->next = left ? left : right;
return dummy->next;
}
};
解法三：二分归并，不太懂
