首页 > 代码库 > Leetcode Merge k Sorted Lists
Leetcode Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
合并k个排序列表
解题思路是：
取出 k个元素进行堆排序，每次取出最小的元素，插入链表中即可
注意本题利用了c++得优先权队列，优先权队列底层是用堆实现的
注意本题中一个特殊的测试用例是[{}]
注意vector为空时表示为[]，而不是[{}],而后者是大小为1的vector，其中元素是空指针
放入优先权队列时进行判断是否为空
放入优先权队列的元素是ListNode *， 而不是int，主要是保持原有链表的地址，避免地址失效，而且放入int话，之后又重新new ListNode(int)开销还是比较大的.
对放入优先权队列中得ListNode*要定义一个比较函数对象，如果不定义的话，比较的是地址大小
class Solution {public: struct cmp{ bool operator()(const ListNode* a, const ListNode* b) const{ return a->val > b->val; } }; ListNode *mergeKLists(vector<ListNode *> &lists) { if(lists.empty()) return NULL; priority_queue<ListNode*,vector<ListNode*>,cmp> pq; ListNode *head = new ListNode(0), *pre = head; for(int i = 0 ; i < lists.size(); ++ i){ if(lists[i]) pq.push(lists[i]); } while(!pq.empty()){ ListNode* node = pq.top(); pq.pop(); if(node->next) pq.push(node->next); pre->next = node; pre = node; } pre->next = NULL; return head->next; }};
第二种方法是二分的方法，每次取两个ListNode * 进行合并
程序中运用了队列，每次从队列中取出两个元素然后合并，将合并后的元素又放入队列，直到队列只剩小一个元素为止即可
class Solution {public: ListNode *mergeLists(ListNode* p,ListNode* q){ ListNode* head = new ListNode(0),*pre = head; while(p && q){ if(p->val < q ->val){ ListNode *tmp = p->next; p->next = pre->next; pre->next = p; pre = p; p = tmp; }else{ ListNode *tmp = q->next; q->next = pre->next; pre->next = q; pre = q; q = tmp; } } pre->next = NULL; if(p) pre->next = p; if(q) pre->next = q; return head->next; } ListNode *mergeKLists(vector<ListNode *> &lists) { if(lists.empty()) return NULL; queue<ListNode *> que; for(int i = 0 ; i < lists.size(); ++ i){ if(lists[i]) que.push(lists[i]); } while(que.size()>1){ ListNode* p = que.front();que.pop(); ListNode* q = que.front();que.pop(); que.push(mergeLists(p,q)); } return que.front(); }};
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。