23. Merge k Sorted Lists
Merge k sorted 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个链表中有的链表全部添加完会变成空链表，应做相应的处理
计算
安全
数据库
网络和加速
企业服务
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize)
{
struct ListNode *list = NULL;
/*获取链表长度*/
int cnt = 0, len = 0;
for ( ; cnt < listsSize; cnt++ )
{
list = lists[cnt];
for ( ; list; list = list->next )
{
len += 1;
}
}
list = NULL;
struct ListNode **head = &list;
struct ListNode *node = NULL;
int key = 0;
for ( cnt = 0; cnt < len; cnt++ )
{
int index = 0;
int nullSizes = 0;
/*获取链表中空链表数量*/
for ( index = 0; index < listsSize; index++ )
{
if ( lists[index] == NULL )
{
nullSizes += 1;
}
}
/*删掉链表数组中空链表，组成新的链表数组*/
int nulls = 0;
int flag = 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;
}
else if ( flag == 1)
{
lists[index] = lists[index + 1];
}
}
}
/*删掉空链表并及时修改现存链表数量*/
if ( flag == 1 )
{
listsSize -= nullSizes;
}
/*找到所有链表中值最小的节点*/
int min = 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;
}
return list;
}亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
