合并K个升序链表
题目链接：合并K个升序链表
问题描述
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4。
解法一（暴力法）
类比合并两个有序列表，可以想出一个暴力的方法，每次选取所有链表的头节点中最小的那个节点，然后被选取的链表往下移动一格节点。这样所有链表都到达末尾后，合并结束。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode* head=new ListNode();
ListNode* L=head;
int len=lists.size();
while(1)
{
int pos=-1;
int minval=INT_MAX;
for(int i=0;i<len;i++)
{
if(lists[i]!=nullptr&&lists[i]->val<minval)
{
pos=i;
minval=lists[i]->val;
}
}
if(pos==-1)
break;
//cout<<lists[pos]->val<<endl;
head->next=new ListNode(lists[pos]->val);
head=head->next;
//cout<<head->val<<endl;
lists[pos]=lists[pos]->next;
}
return L->next;
}
};
解法二（分治）
参考两个有序链表的合并问题，结合分治思想，每次合并两个链表，合并logk次，得到结果。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* merge(ListNode*a ,ListNode *b)
{
ListNode* head=new ListNode();
ListNode* p=head;
while(a!=nullptr&&b!=nullptr)
{
if(a->val<=b->val)
{
p->next=a;
a=a->next;
}
else
{
p->next=b;
b=b->next;
}
p=p->next;
//cout<<p->val<<endl;
}
p->next=(a==nullptr?b:a);
return head->next;
}
ListNode* solve(vector<ListNode*>& lists,int left,int right)
{
//cout<<left<<" "<<right<<endl;
if(right<left)
return nullptr;
if(left==right)
return lists[left];
int mid=(left+right)/2;
return merge(solve(lists,left,mid),solve(lists,mid+1,right));
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
return solve(lists,0,lists.size()-1);
}
};