解法2 直接获取k个节点中的最小节点（堆）

“合并两个升序链表”每次选择两个链表中最小的节点，那么类比到“合并k个升序链表”，可以每次选择k个链表中最小的节点，这个选择可以靠优先级队列（二叉堆） 来实现。

/*** 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:struct Status{int val;ListNode* ptr;bool operator < (const Status &rhs) const{return val > rhs.val;}};priority_queue q;ListNode* mergeKLists(vector& lists) {for(auto node:lists){if(node) q.push({node->val,node});}ListNode head,*tail=&head;while(!q.empty()){auto f=q.top();q.pop();   //取根tail->next=f.ptr;tail=tail->next;if(f.ptr->next) q.push({f.ptr->next->val,f.ptr->next});}return head.next;}
};

复杂度
优先队列q中元素最多有k个，每次pop和push的复杂度为O(logk)，由于所有链表的每一个节点都会push和pop一遍，所以算法的总复杂度为O(nlogk)。

31. 下一个排列

题意

• 相当于找下一个尽可能小的更大的数
• 应当选择最靠右的最左边的较小数与最靠右的尽可能小的数交换，所以选择从右向左遍历寻找目标数。
• 最靠右的最左边的较小数：从右向左寻找第一个升序二元组 ，tar_i=i。
• 最靠右的尽可能小的数：从右往左第一个大于nums[tar_i]的数，记为tar_j。

解法1 分析找规律

例如，452631，应当选择2与3交换。

也就是说，从右向左寻找第一个升序二元组 ，记录tar_i=i，需要注意的是，此时，i的右边一定是一个降序排列。然后再寻找一个比nums[i]大却又尽可能小的数，由于i右边是一个降序排列，所以从右往左寻找第一个大于nums[tar_i]的数即可，记为tar_j。最后，将tar_i右边的数进行升序重排即可。

如果找不到这样一个升序二元组 ，说明此时的序列是一个降序序列，那么下一个排列就是这些数的升序排列，直接重新sort即可。

class Solution {
public:void nextPermutation(vector& nums) {//先不考虑重复数的存在int n=nums.size();int tar_i=-1,tar_j=-1;for(int i=n-2;i>=0;i--){if(nums[i]tar_i=i;break;}}if(tar_i==-1){sort(nums.begin(),nums.end());return ;}for(int i=n-1;i>tar_i;i--){if(nums[i]>nums[tar_i]){tar_j=i;break;}}swap(nums[tar_i],nums[tar_j]);sort(nums.begin()+tar_i+1,nums.end());return ;}
};