23.合并K个排序链表

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

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

考虑合并两个升序链表，可使用一个变量作为衔接，依次合并两个链表，合并K次

合并两个有序链表

ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
    if ((!a) || (!b)) return a ? a : b;
    ListNode head, *tail = &head, *aPtr = a, *bPtr = b;
    while (aPtr && bPtr) {
        if (aPtr->val < bPtr->val) {
            tail->next = aPtr; aPtr = aPtr->next;
        } else {
            tail->next = bPtr; bPtr = bPtr->next;
        }
        tail = tail->next;
    }
    tail->next = (aPtr ? aPtr : bPtr);
    return head.next;
}

依次合并K次

ListNode* mergeKLists(vector<ListNode*>& lists) {
      ListNode *ans = nullptr;
      for (size_t i = 0; i < lists.size(); ++i) {
          ans = mergeTwoLists(ans, lists[i]);
      }
      return ans;
  }

可考虑优先队列（最小堆），将所有<val，结点（链表）>放入优先队列中，每次弹出k个链表首结点值最小的结点，在将此节点的下一个结点放入队列中

class Solution {
public:

struct Compare {
    bool operator()(const pair<int, ListNode*>& a, const pair<int, ListNode*>& b) {
        return a.first > b.first; // 最小堆
    }
};
    ListNode* mergeKLists(vector<ListNode*>& lists) {

        //使用优先队列,最小堆
      priority_queue<pair<int, ListNode*>, vector<pair<int, ListNode*>>, Compare> q;
        for(auto node:lists){
            if(node)q.push({node->val,node});
        }

        ListNode head;
        ListNode* tail=&head;
        while(!q.empty()){
            auto f=q.top();q.pop();
            tail->next=f.second;
            tail=tail->next;
            if(f.second->next)q.push({f.second->next->val,f.second->next});
        }
        return head.next;
    }
};