LeetCode 23.合并K个升序链表

给你一个链表数组每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中返回合并后的链表。示例 1输入lists [[1,4,5],[1,3,4],[2,6]]输出[1,1,2,3,4,4,5,6]解释链表数组如下[1-4-5,1-3-4,2-6]将它们合并到一个有序链表中得到。1-1-2-3-4-4-5-6示例 2输入lists []输出[]示例 3输入lists [[]]输出[]提示k lists.length0 k 10^40 lists[i].length 500-10^4 lists[i][j] 10^4lists[i] 按 升序 排列lists[i].length 的总和不超过 10^4我们可以用小顶堆维护每个链表的头节点然后每次取堆顶的节点加入结果链表/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */classSolution{public:ListNode*mergeKLists(vectorListNode*lists){vectorpairint,inth;for(inti0;ilists.size();i){if(lists[i]!nullptr){h.push_back({lists[i]-val,i});}}make_heap(h.begin(),h.end(),greater());ListNode*ansnullptr;ListNode*curnullptr;while(h.size()0){intminIdxh[0].second;if(ansnullptr){anslists[minIdx];curans;}else{cur-nextlists[minIdx];curcur-next;}pop_heap(h.begin(),h.end(),greater());h.pop_back();lists[minIdx]lists[minIdx]-next;if(lists[minIdx]!nullptr){h.push_back({lists[minIdx]-val,minIdx});push_heap(h.begin(),h.end(),greater());}}returnans;}};如果所有链表中总共有n个节点有个k个链表则此算法时间复杂度为O(knlogk)空间复杂度为O(k)。