#23 Merge k Sorted Lists （N路归并排序）
题目地址：#23 题目分类：链表/归并排序/堆排序 题目难度：hard
题目
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
翻译：合并K个已经排序的链表，返回一个排序好的链表。
思路
暴力法，我们很容易想到：以一个for循环遍历所有的链表，找出最小的，然后将这个节点加入新的链表
时间复杂度： O(k*n)点评：简单粗暴，但是性能实在是太弱了。每次都要遍历所有的链表，测试结果TLE
分治法+归并：对于K个链表，利用分治的思想，每次归并2个直到最后剩下一个排序好的链表
最小堆：参考暴力法，对于这K个链表，每次我们做的操作是：
1 – 找出最小的节点 Node min； 2 – 将Node min加入新的链表 3 – Node min = Node min -> next
在暴力法中，我们的缺陷在于：不能有效地寻找到当前最小的元素。for循环做了许多重复的比较，这无疑是一种浪费 因此，我们预先将节点数组Node [] 构建成最小堆，，然后每次只需要取出第一个元素即可。
时间复杂度： O(k) + O(n*lgk)关于时间复杂度的说明：这里，构建最小堆花费了O(k)时间，而相比于分治法，显然有：
O(k) + O(n*lgk) > O(nlgk)
这样想可就错了。。。思路2中提过，分治归并实际上每次是正正好好的：n*lgk次遍历元素次数+n*lgk次比较次数 相比之下，最小堆除了第一次建队的开销外，其余的开销都在维护堆上。所以这个O(n*lgk)应该是——每个元素最多进行lgk次比较（最坏情况）+每个元素遍历1次 因此，最小堆在大量数据情况下，绝对是优于分治归并的！点评：最小堆复杂在建堆+维护堆，但是性能的提升是很大的。更好的方法——Loser Tree
待补充
陷阱
对于难题，反而考察的是算法的实现，没有什么小坑可以跳了。 这里只需要注意NULL指针的处理即可。 我选用的方法是，将NULL指针替换为一个value = INT_MAX的节点 这样这个节点只会被沉到堆底，不需要浪费比较次数 终止条件设为：首元素为这个INT_MAX节点
对于这个思路，想到了一些数组方面的排序问题的边界处理。**如果你要在一个数组中寻找某个数字，常规的做法是 for(int i=0;i！=size;i++){if(a[i]==flag)…} 但是这样每次都需要比较size和i。可以这样做：边界处放置一个flag，一旦a[i] == flag, 就可以退出循环了。 以上为题外话
测试案例输入整个为NULL输入的数组中含有为NULL的链表性能测试，OJ的测试案例包含了10000个链表 代码
C
void MIN_HEAP_SORT(struct ListNode **lists, int index_i,int size){int left = index_i*2 + 1;int right= index_i*2 + 2;if(left>=size)return;int min;if(right>=size)min = left;elsemin = lists[left]->val<lists[right]->val?left:right;if(lists[index_i]->val>lists[min]->val){struct ListNode *temp = lists[index_i];lists[index_i] = lists[min];lists[min] = temp;MIN_HEAP_SORT(lists,min,size);}}void BuildHeap(struct ListNode **lists,int size){for(int i=(size-1)/2;i>=0;–i){MIN_HEAP_SORT(lists,i,size);}}struct ListNode *mergeKLists(struct ListNode *lists[], int k) {if(k==0)return NULL;//1struct ListNode *head = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode *int_max = (struct ListNode*)malloc(sizeof(struct ListNode));int_max->val = INT_MAX;int_max->next = NULL;struct ListNode *travel = head;for(int i=0;i<k;++i){if(lists[i]==NULL)lists[i] = int_max;}/*remove those NULL ptr*/BuildHeap(lists,k);while(lists[0]!=int_max){travel->next = lists[0];travel = lists[0];lists[0] = lists[0]->next;if(lists[0]==NULL)lists[0] = int_max;MIN_HEAP_SORT(lists,0,k);}travel->next = NULL;return head->next;}LeetCode上的其他解法
黑夜下，撕开那张面具尽是怠倦的容颜，
