【LeetCode】23. Merge k Sorted Lists 分治
【LeetCode】23. Merge k Sorted Lists 分治
韩旭051
发布于 2020-06-23 11:09:23
发布于 2020-06-23 11:09:23
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/merge-k-sorted-lists 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
分治第一道题，这道题还是主要看大家的答案做上来的~
学到的知识点有 c++语法
1.申请内存直接
new ListNode *head = new ListNode(0);2. 向量vector 转双端队列
queue<ListNode*> waiting(deque<ListNode*>(lists.begin(), lists.end())); //将vector转为队列3.合并链表到最后小尾巴这里可以一步解决
p->next = l1 ? l1 : l2;
return head->next;整一个空节点存头，最后返回空节点的下一个就是头
return head->next;4.队列的神奇用法 pop两次融合成一个再push进去
while (waiting.size() > 1) {
ListNode *l1 = waiting.front();
waiting.pop();
ListNode *l2 = waiting.front();
waiting.pop();
waiting.push(merge2(l1, l2));
} 放代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.size()==0){return NULL;}
if(lists.size()==1){return lists[0];}
queue<ListNode*> que(deque(lists.begin(),lists.end()));
while(que.size()>1){
ListNode* p1 =que.front();
que.pop();
ListNode* p2 =que.front();
que.pop();
que.push(mergelink(p1,p2));
}
return que.front();
}
ListNode* mergelink(ListNode* p1,ListNode*p2){
ListNode* head = new ListNode(0);
ListNode* p=head;
while(p1&&p2){
if(p1->val>p2->val){
p->next=p2;
p=p->next;
p2=p2->next;
}else{
p->next=p1;
p=p->next;
p1=p1->next;
}
}
p->next= p1? p1:p2;
return head->next;
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-12-09 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录