网页网站公司如何做备份,游戏型网站开发,wordpress 云落主题,网站建设续签合同怎么签文章目录1. 题目信息2. 思路3. 代码1. 题目信息
合并 k 个排序链表#xff0c;返回合并后的排序链表。请分析和描述算法的复杂度。
示例:输入:
[1-4-5,1-3-4,2-6
]
输出: 1-1-2-3-4-4-5-6来源#xff1a;力扣#xff08;…
文章目录1. 题目信息2. 思路3. 代码1. 题目信息
合并 k 个排序链表返回合并后的排序链表。请分析和描述算法的复杂度。
示例:输入:
[1-4-5,1-3-4,2-6
]
输出: 1-1-2-3-4-4-5-6来源力扣LeetCode 链接https://leetcode-cn.com/problems/merge-k-sorted-lists 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 思路
建立优先队列小顶堆将每个链表的队首指针push进入优先队列O(k)取出堆顶读取堆顶的值插入新的链表O(1)将堆顶的next指针如果存在push进入优先队列O(logk)弹出堆顶O(logk)循环以上 3-6 复杂度*n(总的结点个数) 总的时间复杂度O(n • logk)
3. 代码 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution
{
public:struct cmp{bool operator()(ListNode *a, ListNode *b){return a-val b-val;}};ListNode* mergeKLists(vectorListNode* lists){priority_queueListNode*, vectorListNode*, cmp queue;ListNode *head new ListNode(0);ListNode *temp head, *topNext;for(int i 0; i lists.size(); i){if(lists[i])queue.push(lists[i]);}while(!queue.empty()){temp-next queue.top();temp temp-next;topNext queue.top()-next;queue.pop();if(topNext)queue.push(topNext);}return head-next;}
};
