用优先队列维护 ListNode*,根据其 val 值做小顶堆,每一次都取小顶堆堆订连接上即可
class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { priority_queue<ListNode*, vector<ListNode*>, Compare> pq; for(auto &item : lists){ if(item) pq.push(item); } ListNode *head = new ListNode, *temp = head; while(!pq.empty()) { auto top = pq.top(); pq.pop(); temp -> next = top; top = top -> next; temp = temp -> next; if(top) pq.push(top); } auto ret = head -> next; delete head; return ret; } struct Compare { bool operator()(ListNode *l1, ListNode *l2) { return l1 -> val > l2->val; } }; };