題目
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
分析
合并k個(gè)排序的鏈表，返回已排序的結(jié)果。
對K個(gè)鏈表依次遍歷另假，找到最小值营曼，然后放入結(jié)果鏈表中岸夯，最后K個(gè)鏈表沒有元素的時(shí)候退出读第。
/**
* 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;
}
