LeetCode----Merge K sorted Lists

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

采用最小堆，首先将 k 个首节点放入堆中，弹出最小的节点并插入到新的链表中；

弹出的节点如果next 非空，就将它的 下一个节点进 堆。

继续，直到堆为空。

堆 Push 和 pop 的复杂度是 log(k), 所以复杂度是 nlg(k), n为总的节点数；

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *mergeKLists(vector
  
    &lists) {
        int K = lists.size();
        if (K == 0) return NULL;
        else if (K == 1) return lists[0];
        
        ListNode *listHead(NULL), *listRear(NULL);
        ListNode *node(NULL);
        priority_queue
   
    , cmp> h; // push K list heads into heap for(int i=0; i
    
     next; } while(!h.empty()){ //pop the min of k nodes node = h.top(); h.pop(); if(node->next) h.push(node->next); //insert node into new list if(listRear){ listRear->next = node; listRear = listRear->next; } else{ listHead = listRear = node; } } return listHead; } private: struct cmp{ bool operator()(ListNode* lhs, ListNode *rhs){ if(lhs->val < rhs->val) return false; else return true; } }; };