Merge k Sorted Lists

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

 1 /** 2  * Definition for singly-linked list. 3  * struct ListNode { 4  *     int val; 5  *     ListNode *next; 6  *     ListNode(int x) : val(x), next(NULL) {} 7  * }; 8  */ 9  10 struct cmp11 {12     bool operator()(ListNode *a,ListNode *b)13     {14         //升序，每次优先队列返回最小的15         return a->val>b->val;16     }17 };18  19 class Solution {20    21    22 public:23     ListNode *mergeKLists(vector<ListNode *> &lists) {24        25         priority_queue<ListNode *,vector<ListNode*>,cmp> q;26        27         for(int i=0;i<lists.size();i++)28         {29             if(lists[i]!=NULL) q.push(lists[i]);30         }31        32         ListNode *front=new ListNode(0);33         ListNode *result;34         result=front;35        36         while(!q.empty())37         {38             ListNode *tmp=q.top();39             front->next=tmp;40             if(tmp->next!=NULL) q.push(tmp->next);41             q.pop();42             front=tmp;43         }44        45         front->next=NULL;46        47         ListNode *tmp=result;48         result=result->next;49         delete tmp;50         return result;51        52     }53 };