[LeetCode]23.MergekSortedLists
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; }
本文标题:[LeetCode]23.MergekSortedLists
网页路径:http://ybzwz.com/article/jjoesg.html