[offer78] merge multiple ordered linked lists

Merge multiple ordered linked lists

subject

Given a linked list array , Each list has been listed in ascending order .

Please merge all linked lists into one ascending linked list , Return the merged linked list .

Example 1：

Input ：lists = [[1,4,5],[1,3,4],[2,6]]
Output ：[1,1,2,3,4,4,5,6]
explain ： The linked list array is as follows ：
[
1->4->5,
1->3->4,
2->6
]
Combine them into an ordered list to get .
1->1->2->3->4->4->5->6
Example 2：

Input ：lists = []
Output ：[]
Example 3：

Input ：lists = [[]]
Output ：[]

Tips ：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] Press Ascending array
lists[i].length The sum of is not more than 10^4

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/vvXgSW
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

/* Method ： Priority queue */
#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) {
    }
};

/* Preliminary knowledge ： Function object 、 Class template 、 Anonymous object 、 The function of single chain header node 、priorty_queue Basic operation */
/* One . Priority queue （priority_queue) Initialization of requires the use of function objects , The function is to set how to judge the priority size of two elements in the heap , By default less<T>()*/
/* Two . Something that can act as a function object ： Ordinary function 、 Reload the （） Class  * 1. Use normal functions ： Pass in the function name directly  * 2. Use class ： Pass in an object of this class , Anonymous objects are generally used , That is, the class name （） * 3. The function object passed into the priority queue needs to be consistent with the required format . */
/* 3、 ... and . see prior_queue If you have a template , The last two parameter types have default values  *  If you use the default type . You need to implement the < overloaded  */

/* Prepare the function object */
struct cmp {
    
	bool operator ()(ListNode* a, ListNode* b) {
    
	    /* return true Under the circumstances , This element moves down in the heap */
		return a->val > b->val;
	}
};

class Solution {
    
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
    
		/* The idea is to put all pointers in a priority queue  *  The top of the heap has the highest priority . *  Every time the top of the stack is ejected  *  Then judge whether there are subsequent nodes , If there is , stay push Come in , Priority queues restructure the heap  */
		priority_queue<ListNode*,vector<ListNode*>,cmp> queue;
		for (auto node : lists) {
    
			/* It has been stated in the title that an empty linked list may be introduced */
			if (node)
				queue.push(node);
		}

		/* Define the storage location of results , First define the header node , And its corresponding pointer ( For unified operation ）*/
		ListNode ans, * cur=&ans;

		/* The final situation is that the queue is empty */
		while (!queue.empty()) {
    
			/* Don't think about taking a direct step pop,pop no return value */
			ListNode* temp = queue.top();
			queue.pop();
			/* Direct operation head pointer , To take out temp Receive ans Back */
			cur->next = temp;
			/* Move the pointer to the end of the linked list , In order to continue splicing */
			cur = cur->next;
			if (temp->next)
				queue.push(temp->next);
		}
		/* The header node has no practical significance . Don't go back */
		return ans.next;
    }
};