C++中优先队列的用法和普通队列无异,注意比较方式的写法:
//升序队列 priority_queue <int,vector<int>,greater<int> > q; //降序队列 priority_queue <int,vector<int>,less<int> >q; //greater和less是std实现的两个仿函数
在这里我们需要自定义比较,代码如下:
struct comp{ // 自定义比较 bool operator()(ListNode *a, ListNode *b) { return a->val > b->val; } }; class Solution { public: ListNode *mergeKLists(vector<ListNode *> &lists) { priority_queue<ListNode*, vector<ListNode *>, comp> pq; for (int i = 0; i < lists.size(); ++i) if (lists[i] != NULL) pq.push(lists[i]); ListNode dummyHead(0); ListNode *p = &dummyHead; while(!pq.empty()) { ListNode *q = pq.top(); pq.pop(); if (q->next) pq.push(q->next); // 放回 p = p->next = q; } return dummyHead.next; } };