LeetCode Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

题意：将k个已经排好序的链表合并成一个

思路：用到优先队列比较简单。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
struct cmp{
    bool operator() (ListNode *a, ListNode *b) {
        return a->val > b->val;
    }
};

class Solution {
public:
    ListNode *mergeKLists(vector
  
    &lists) {
        priority_queue
   
    , cmp> queue; for (int i = 0; i < lists.size(); i++) { if (lists[i] != NULL) queue.push(lists[i]); } ListNode *head = NULL, *pre = NULL, *tmp; while (!queue.empty()) { tmp = queue.top(); queue.pop(); if (pre == NULL) head = tmp; else pre->next = tmp; pre = tmp; if (tmp->next != NULL) queue.push(tmp->next); } return head; } };