23. Merge k Sorted Lists

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


给定k个排序了的链表，合并k个链表成一个排序链表。


本程序思路：

1）首先得到K个链表的长度和存在len中

2）从K个链表中找到值最小的那个节点，把该节点添加到合并链表中

3）重复len次即可把所有节点添加到合并链表中。


注意事项：

1）K个链表中有的链表全部添加完会变成空链表，应做相应的处理

/***Definitionforsingly-linkedlist.*structListNode{*intval;*structListNode*next;*};*/structListNode*mergeKLists(structListNode**lists,intlistsSize){structListNode*list=NULL;/*获取链表长度*/intcnt=0,len=0;for(;cnt<listsSize;cnt++){list=lists[cnt];for(;list;list=list->next){len+=1;}}list=NULL;structListNode**head=&list;structListNode*node=NULL;intkey=0;for(cnt=0;cnt<len;cnt++){intindex=0;intnullSizes=0;/*获取链表中空链表数量*/for(index=0;index<listsSize;index++){if(lists[index]==NULL){nullSizes+=1;}}/*删掉链表数组中空链表，组成新的链表数组*/intnulls=0;intflag=0;for(nulls=0;nulls<nullSizes;nulls++){flag=0;for(index=0;index<listsSize;index++){if(lists[index]==NULL){lists[index]=lists[index+1];flag=1;}elseif(flag==1){lists[index]=lists[index+1];}}}/*删掉空链表并及时修改现存链表数量*/if(flag==1){listsSize-=nullSizes;}/*找到所有链表中值最小的节点*/intmin=INT_MAX;for(index=0;index<listsSize;index++){if(lists[index]->val<min){min=lists[index]->val;node=lists[index];key=index;}}/*把最小节点添加到合并链表中*/(*head)=node;node=node->next;head=&(*head)->next;/*最小值所在链表往后移*/lists[key]=node;}returnlist;}