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; } };