Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
两个方法： 方法1. 利用 STL 中的 multiset (根据结点内的值)自动对指针排序。空间 O(N), 时间 O(NlogN).
(亦可用于 k 个无序链表)。（AC: 164ms）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
bool compare (const ListNode *p1, const ListNode *p2) {
return p1->val < p2->val;
}
class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
typedef bool (*cmp) (const ListNode *p1, const ListNode *p2);
multiset<ListNode*, cmp> container(compare);
for(size_t i = 0; i < lists.size(); ++i) {
ListNode *p = lists[i];
while(p) { container.insert(p); p = p->next; }
}
ListNode *head = NULL, *p = head;
for(auto it = container.begin(); it != container.end(); ++it) {
if(p) { p->next = *it; p = *it; }
else p = head = *it;
}
if(p) p->next = NULL;
return head;
}
};
方法2. 不利用任何 STL 函数。对指针建堆排序，只需要一个(win32: 4Byte)指针数组即可。空间 : O(K), 时间 O(NlogK)
(AC: 140ms)
最初代码：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
heap = vector<ListNode*>(lists.size(), );
sz = ;
for(size_t i = ; i < lists.size(); ++i)
if(lists[i]) push(lists[i]);
ListNode *head = NULL, *p = head;
while(sz) {
if(head == NULL)
p = head = pop();
else {
p->next = pop();
p = p->next;
}
if(p->next) push(p->next);
}
return head;
}
void push(ListNode *p) {
int child = sz++;
while(child > ) {
int father = (child-) / ;
if(p->val >= heap[father]->val) break;
heap[child] = heap[father];
child = father;
}
heap[child] = p;
}
ListNode* pop() {
ListNode *pAns = heap[];
heap[] = heap[--sz];
int father = , child = ;
ListNode *p = heap[father];
while(child < sz) {
if(child+ < sz && heap[child]->val > heap[child+]->val) ++child;
if(heap[child]->val >= p->val) break;
heap[father] = heap[child];
father = child;
child = * father + ;
}
heap[father] = p;
return pAns;
}
private:
int sz;
vector<ListNode*> heap;
};
优化后（增强易读性）：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Heap {
public:
Heap(size_t n) : sz(0), heap(vector<ListNode*>(n, NULL)) {}
void push(ListNode *p);
ListNode* pop();
int size() { return sz; }
private:
int sz;
vector<ListNode*> heap;
};
inline void Heap::push(ListNode *p) {
int child = sz++;
while(child > 0) {
int father = (child-1) / 2;
if(p->val >= heap[father]->val) break;
heap[child] = heap[father];
child = father;
}
heap[child] = p;
}
inline ListNode* Heap::pop() {
ListNode *pAns = heap[0];
heap[0] = heap[--sz];
int father = 0, child = 1;
ListNode *p = heap[father];
while(child < sz) {
if(child+1 < sz && heap[child]->val > heap[child+1]->val) ++child;
if(heap[child]->val >= p->val) break;
heap[father] = heap[child];
father = child;
child = 2 * father + 1;
}
heap[father] = p;
return pAns;
}
class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
Heap heap(lists.size());
for(size_t i = 0; i < lists.size(); ++i)
if(lists[i]) heap.push(lists[i]);
ListNode *head = NULL, *p = head;
while(heap.size()) {
if(head == NULL)
p = head = heap.pop();
else {
p->next = heap.pop();
p = p->next;
}
if(p->next) heap.push(p->next);
}
return head;
}
};