# [Leetcode 23]合并K个升序链表（优先队列）

## 题面

• 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

## 代码

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43  /** * 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 cmp { bool operator () (const ListNode *a, const ListNode *b) { return a->val > b->val; } }; const int INF = 0x3f3f3f3f; ListNode* mergeKLists(vector& lists) { ListNode head(INF, nullptr); ListNode *now = &head; priority_queue, cmp> q; int k = lists.size(); for(int i = 0; i < k; i++) { if(lists[i] != nullptr) { q.push(lists[i]); } } while(!q.empty()) { now->next = q.top(); now = now->next; q.pop(); if(now->next != nullptr) { q.push(now->next); } } return head.next; } };