[offer78]合并多个有序链表

合并多个有序链表

题目

给定一个链表数组，每个链表都已经按升序排列。

请将所有链表合并到一个升序链表中，返回合并后的链表。

示例 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.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/vvXgSW
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/*方法：优先队列*/
#include <vector>
#include<queue>
#include<iostream>
using namespace std;

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) {
    }
};

/*预备知识：函数对象、类模板、匿名对象、单链表头结点的作用、priorty_queue基本操作*/
/*一。优先队列（priority_queue)的初始化需要使用到函数对象，作用是设置如何判断堆中两个元素的优先级大小，默认使用less<T>()*/
/*二。可以充当函数对象的东西：普通函数、重载了（）的类 * 1.使用普通函数：直接传入函数名 * 2.使用类：传入该类的一个对象，一般使用匿名对象，即类名（） * 3.传入优先级队列的函数对象需要和所要求的格式一致。 */
/*三。查看prior_queue的模板的话，后两个参数类型是有默认值的 * 如果使用默认类型。需要在自定义类中自行实现对<的重载 */

/*准备函数对象*/
struct cmp {
    
	bool operator ()(ListNode* a, ListNode* b) {
    
	    /*返回true的情况下，该元素在堆中下移*/
		return a->val > b->val;
	}
};

class Solution {
    
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
    
		/*思路就是把所有的指针都放在一个优先队列中 * 堆顶存放优先级最高的。 * 每次弹出堆顶 * 再判断其是否还有后续结点，如果有，在push进来，优先队列重新调整堆的结构 */
		priority_queue<ListNode*,vector<ListNode*>,cmp> queue;
		for (auto node : lists) {
    
			/*题目中已经说明可能会传入空链表了*/
			if (node)
				queue.push(node);
		}

		/*定义结果存放位置,先定义头结点，及其对应的指针(为了统一操作）*/
		ListNode ans, * cur=&ans;

		/*最终的情况就是队列为空*/
		while (!queue.empty()) {
    
			/*不用想直接一步pop，pop没有返回值*/
			ListNode* temp = queue.top();
			queue.pop();
			/*直接操作头指针，将取出的temp接到ans后面*/
			cur->next = temp;
			/*移动指针到链表末端,以便继续拼接*/
			cur = cur->next;
			if (temp->next)
				queue.push(temp->next);
		}
		/*头结点没有实际意义。不用返回*/
		return ans.next;
    }
};