建站
咨詢
售后
建站咨詢
新聞中心
這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷解決方案
[LeetCode]23.MergekSortedLists
23. Merge k Sorted Lists
在崗巴等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場(chǎng)前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供成都做網(wǎng)站、成都網(wǎng)站制作 網(wǎng)站設(shè)計(jì)制作定制開發(fā),公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),成都品牌網(wǎng)站建設(shè),全網(wǎng)整合營(yíng)銷推廣,成都外貿(mào)網(wǎng)站建設(shè),崗巴網(wǎng)站建設(shè)費(fèi)用合理。
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
給定k個(gè)排序了的鏈表，合并k個(gè)鏈表成一個(gè)排序鏈表。
本程序思路：
1）首先得到K個(gè)鏈表的長(zhǎng)度和存在len中
2）從K個(gè)鏈表中找到值最小的那個(gè)節(jié)點(diǎn)，把該節(jié)點(diǎn)添加到合并鏈表中
3）重復(fù)len次即可把所有節(jié)點(diǎn)添加到合并鏈表中。
注意事項(xiàng)：
1）K個(gè)鏈表中有的鏈表全部添加完會(huì)變成空鏈表，應(yīng)做相應(yīng)的處理
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize)
{
struct ListNode *list = NULL;
/*獲取鏈表長(zhǎng)度*/
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;
/*獲取鏈表中空鏈表數(shù)量*/
for ( index = 0; index < listsSize; index++ )
{
if ( lists[index] == NULL )
{
nullSizes += 1;
}
}
/*刪掉鏈表數(shù)組中空鏈表，組成新的鏈表數(shù)組*/
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];
}
}
}
/*刪掉空鏈表并及時(shí)修改現(xiàn)存鏈表數(shù)量*/
if ( flag == 1 )
{
listsSize -= nullSizes;
}
/*找到所有鏈表中值最小的節(jié)點(diǎn)*/
int min = INT_MAX;
for ( index = 0; index < listsSize; index++ )
{
if ( lists[index]->val < min )
{
min = lists[index]->val;
node = lists[index];
key = index;
}
}
/*把最小節(jié)點(diǎn)添加到合并鏈表中*/
(*head) = node;
node = node->next;
head = &(*head)->next;
/*最小值所在鏈表往后移*/
lists[key] = node;
}
return list;
}
文章題目：[LeetCode]23.MergekSortedLists
網(wǎng)站鏈接：http://ef60e0e.cn/article/jjoesg.html
