Description:
Merge k sorted linked lists and return it as one sorted list.
Analyze and describe its complexity.
Example:
Given lists:
[
2->4->null,
null,
-1->null
],
return -1->2->4->null.
Link:
http://www.lintcode.com/en/problem/merge-k-sorted-lists/
解题思路：
使用堆排序可以解决
Time Complexity：
O(kn)
完整代码：
struct compare { bool operator ()(ListNode *a, ListNode *b) { return a->val > b->val; } }; class Solution { public: ListNode *mergeKLists(vector<ListNode *> &lists) { if(lists.size() == 0) return NULL; priority_queue <ListNode *, vector<ListNode *>, compare> pq; for(int i = 0; i < lists.size(); i++) { ListNode *temp = lists[i]; while(temp != NULL) { pq.push(temp); temp = temp->next; } } ListNode *dummy = new ListNode(0); ListNode *tail = dummy; while(!pq.empty()) { tail->next = pq.top(); pq.pop(); tail = tail->next; } return dummy->next; } };
