Merge k Sorted Lists

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

 /**

  * 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<ListNode *> &lists) {

         priority_queue<ListNode *,vector<ListNode*>,cmp> q;

         for(int i=;i<lists.size();i++)

         {

             if(lists[i]!=NULL) q.push(lists[i]);

         }

         ListNode *front=new ListNode();

         ListNode *result;

         result=front;

         while(!q.empty())

         {

             ListNode *tmp=q.top();

             front->next=tmp;

             if(tmp->next!=NULL) q.push(tmp->next);

             q.pop();

             front=tmp;

         }

         front->next=NULL;

         ListNode *tmp=result;

         result=result->next;

         delete tmp;

         return result;

     }

 };