Leetcode 23.合并K个排序链表 发表于 2019-05-04 | 更新于 2020-04-13 | 分类于 Leetcode 题目描述合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 1234567输入:[ 1->4->5, 1->3->4, 2->6]输出: 1->1->2->3->4->4->5->6 题目分析同 Leetcode 21.合并两个有序链表, 将所有节点放入优先队列后建新表. 源码123456789101112131415161718192021222324252627282930313233struct comp{ // 自定义排序函数 bool operator()(ListNode* &a, ListNode* &b) { return a->val > b->val; }};class Solution {public: priority_queue<ListNode*, vector<ListNode*>, comp> q; // 用优先队列储存节点 ListNode* mergeKLists(vector<ListNode*>& lists) { if(lists.size() == 0) return NULL; // 如果数组为空则返回NULL ListNode* it; for(int i=0; i<lists.size(); ++i) { // 遍历所有表并将每个表中所有节点存入优先队列 it = lists[i]; while(it != NULL) { q.push(it); it = it->next; } } if(q.size() == 0) return NULL; // 如果数组中只有空节点则返回NULL ListNode* res = q.top(); q.pop(); it = res; while(q.size() != 0) { it->next = q.top(); it = it->next; q.pop(); } it->next = NULL; // ***将最后一个节点的next设为NULL*** return res; }};