问题：
给定k个有序链表，将这些链表的所有节点排序，组合成一个新的有序链表。
Example 1: Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] Explanation: The linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted list: 1->1->2->3->4->4->5->6 Example 2: Input: lists = [] Output: [] Example 3: Input: lists = [[]] Output: [] Constraints: k == lists.length 0 <= k <= 10^4 0 <= lists[i].length <= 500 -10^4 <= lists[i][j] <= 10^4 lists[i] is sorted in ascending order. The sum of lists[i].length won‘t exceed 10^4.
解法：Min Heap (最小堆)
首先最小堆的实现：
class minHeap { private: vector<ListNode*> heapary; public: int n; //size minHeap() { n=0; } };
操作：
1 void push(ListNode* val) { 2 heapary.push_back(val); 3 n++; 4 swim(n-1); 5 } 6 ListNode* popmin() { 7 ListNode* res = heapary[0]; 8 if(heapary[0]->next==NULL) { 9 swap(heapary[0], heapary[n-1]); 10 heapary.pop_back(); 11 n--; 12 } else { 13 heapary[0] = heapary[0]->next; 14 } 15 sink(0); 16 return res; 17 }
堆适应化：
1 void swim(int i) { 2 int father = parent(i); 3 while(father>=0 && heapary[father]->val > heapary[i]->val) { 4 swap(heapary[father], heapary[i]); 5 i = father; 6 father = parent(i); 7 } 8 } 9 void sink(int i) { 10 int l = left(i); 11 int r = right(i); 12 int minchild; 13 while(l<n) { 14 minchild = l; 15 if(r<n && heapary[r]->val<heapary[minchild]->val) { 16 minchild = r; 17 } 18 if(heapary[minchild]->val >= heapary[i]->val) break; 19 swap(heapary[minchild], heapary[i]); 20 i = minchild; 21 l = left(i); 22 r = right(i); 23 } 24 }
另外，这里常用求node i 的父节点，子节点：
1 int parent(int i) { 2 return (i-1)/2; 3 } 4 int left(int i) { 5 return i*2+1; 6 } 7 int right(int i) { 8 return i*2+2; 9 }
对本题：
利用上述最小堆，将每个list的头节点放入堆中push(list)，
每次弹出堆顶popmin，作为当前最小值，
?? 注意：
每次，将上次弹出的最小值->next=本次弹出的当前最小值
最终得到所求结果。
代码参考：
1 class Solution { 2 public: 3 ListNode* mergeKLists(vector<ListNode*>& lists) { 4 minHeap mh; 5 ListNode* res = NULL, *p = NULL; 6 for(ListNode* list : lists) { 7 if(list) mh.push(list); 8 } 9 while(mh.n>0) { 10 if(!res) { 11 res = mh.popmin(); 12 p = res; 13 } else { 14 p->next = mh.popmin(); 15 p = p->next; 16 } 17 } 18 return res; 19 } 20 };
leetcode解答完整代码：
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode() : val(0), next(nullptr) {} 7 * ListNode(int x) : val(x), next(nullptr) {} 8 * ListNode(int x, ListNode *next) : val(x), next(next) {} 9 * }; 10 */ 11 class minHeap { 12 private: 13 vector<ListNode*> heapary; 14 int parent(int i) { 15 return (i-1)/2; 16 } 17 int left(int i) { 18 return i*2+1; 19 } 20 int right(int i) { 21 return i*2+2; 22 } 23 void swim(int i) { 24 int father = parent(i); 25 while(father>=0 && heapary[father]->val > heapary[i]->val) { 26 swap(heapary[father], heapary[i]); 27 i = father; 28 father = parent(i); 29 } 30 } 31 void sink(int i) { 32 int l = left(i); 33 int r = right(i); 34 int minchild; 35 while(l<n) { 36 minchild = l; 37 if(r<n && heapary[r]->val<heapary[minchild]->val) { 38 minchild = r; 39 } 40 if(heapary[minchild]->val >= heapary[i]->val) break; 41 swap(heapary[minchild], heapary[i]); 42 i = minchild; 43 l = left(i); 44 r = right(i); 45 } 46 } 47 public: 48 int n; 49 minHeap() { 50 n=0; 51 } 52 void push(ListNode* val) { 53 heapary.push_back(val); 54 n++; 55 swim(n-1); 56 } 57 ListNode* popmin() { 58 ListNode* res = heapary[0]; 59 if(heapary[0]->next==NULL) { 60 swap(heapary[0], heapary[n-1]); 61 heapary.pop_back(); 62 n--; 63 } else { 64 heapary[0] = heapary[0]->next; 65 } 66 sink(0); 67 return res; 68 } 69 }; 70 71 class Solution { 72 public: 73 ListNode* mergeKLists(vector<ListNode*>& lists) { 74 minHeap mh; 75 ListNode* res = NULL, *p = NULL; 76 for(ListNode* list : lists) { 77 if(list) mh.push(list); 78 } 79 while(mh.n>0) { 80 if(!res) { 81 res = mh.popmin(); 82 p = res; 83 } else { 84 p->next = mh.popmin(); 85 p = p->next; 86 } 87 } 88 return res; 89 } 90 };
原文：https://www.cnblogs.com/habibah-chang/p/13872476.html
