Merge k Sorted Lists
Desicription
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
|
class Solution { private: struct cmp{ bool operator()(ListNode const *a, ListNode const *b){ return a->val > b->val; } };
public: ListNode* mergeKLists(vector<ListNode*>& lists) { ListNode *head = new ListNode(0); ListNode *now(head); priority_queue<ListNode*, vector<ListNode*>, cmp>Q; for(int i = 0; i < lists.size(); i++) if(lists[i]) Q.push(lists[i]); while(!Q.empty()){ ListNode *top = Q.top(); Q.pop(); now->next = new ListNode(0); now->next->val = top->val; now = now->next; if(top->next) Q.push(top->next); } return head->next; } };
|