题目
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
分析
合并k个排序的链表，返回已排序的结果。
对K个链表依次遍历，找到最小值，然后放入结果链表中，最后K个链表没有元素的时候退出。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
struct ListNode *ans=NULL,*last;
while(1)
{
int min=1000000,mink=-1;
for(int i=0;i<listsSize;i++)
{
if(lists[i]!=NULL&&lists[i]->val<min)
{
min=lists[i]->val;
mink=i;
}
}
//printf("%d %d\n",min,mink);
if(mink==-1)break;
lists[mink]=lists[mink]->next;
struct ListNode *temp=(struct ListNode *)malloc(sizeof(struct ListNode));
temp->val=min;
temp->next=NULL;
if(ans==NULL)
{
ans=temp;
last=ans;
}
else
{
last->next=temp;
last=temp;
}
}
return ans;
}
