首页 > 代码库 > 71. Merge k Sorted Lists
71. Merge k Sorted Lists
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)
最初代码：
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 class Solution {10 public:11 ListNode *mergeKLists(vector<ListNode *> &lists) {12 heap = vector<ListNode*>(lists.size(), 0);13 sz = 0;14 for(size_t i = 0; i < lists.size(); ++i) 15 if(lists[i]) push(lists[i]);16 ListNode *head = NULL, *p = head;17 while(sz) {18 if(head == NULL) 19 p = head = pop();20 else { 21 p->next = pop();22 p = p->next;23 }24 if(p->next) push(p->next);25 }26 return head;27 }28 void push(ListNode *p) {29 int child = sz++;30 while(child > 0) {31 int father = (child-1) / 2;32 if(p->val >= heap[father]->val) break;33 heap[child] = heap[father];34 child = father;35 }36 heap[child] = p;37 }38 ListNode* pop() {39 ListNode *pAns = heap[0];40 heap[0] = heap[--sz];41 int father = 0, child = 1;42 ListNode *p = heap[father];43 while(child < sz) {44 if(child+1 < sz && heap[child]->val > heap[child+1]->val) ++child;45 if(heap[child]->val >= p->val) break;46 heap[father] = heap[child];47 father = child;48 child = 2 * father + 1;49 }50 heap[father] = p;51 return pAns;52 }53 private:54 int sz;55 vector<ListNode*> heap;56 };
优化后（增强易读性）：
/** * 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; }};
71. Merge k Sorted Lists
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。