本文主要是介绍【链表】Leetcode 合并k个升序链表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目讲解
23. 合并 K 个升序链表
算法讲解
首先将所有链表的当前首节点找出来,判断当前的结点哪一个最小,链接到结果链表的后面,但是怎么寻找当前的最小结点:就需要使用优先级队列,我们建立一个小堆,然后取出堆顶的结点链接到结果链表的后面。
注意:遍历一次vector后现在的队列里面全保存的当前的首节点,所以我们之后不在需要遍历vector了,因为取出当前的top之后,我们让当前top节点的之后向后移动一位,然后再push到堆里,只有当堆为空的时候才是所有的链表都遍历完成的时候
/*** 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) {}* };*/
class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {//暴力解法的优化:每一次循环取出当前链表的的第一个结点,判断每一个结点的最小值,放到ret链表后面//为了寻找出最小的Node,使用优先级队列ListNode* newhead = new ListNode(-1);ListNode* phead = newhead;priority_queue<ListNode*,vector<ListNode*>, function<bool(ListNode*, ListNode*)>>que([](ListNode* n1, ListNode* n2){return n1->val > n2->val;});for(ListNode* head : lists){//这里的hhead是每一个链表的当前结点if(head){que.push(head);}}//走到这里 小堆里面充满了当前所有链表的首节点while(!que.empty()){//将小堆 顶部的Node链接在结果后面ListNode* temp = que.top();que.pop();phead->next = temp;phead = phead->next;//重新将temp链表的指针向后移动一步,添加到队列里if(temp->next) que.push(temp->next);}phead = newhead->next;delete newhead;return phead;}
};
这篇关于【链表】Leetcode 合并k个升序链表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!