之前面试的时候遇到了算法的问题，想了很久都没有想出最好的方案，最终还是放弃了，最后想想，毕竟没有要求我当场写代码，就这样认输真心有点佩服自己。
非递归做法
非递归的做法思想是：先判断两个链表头，以决定哪个链表头作为新链表的链表头指针；然后同时遍历两个链表，直到其中一个链表尾，比较时，值小的接入到新的链表中，同时向后移动该链表的头指针和新链表的指针；当遍历完毕后，哪个链表不为空，就直接将剩余部分接入到新链表尾即可。递归做法
递归做法，
其实就是每次判断哪个值小，值小的作为头，然后递归构造next部分。
求最小的K个数
100w个数中找出最大的100个数。
方案1：在前面的题中，我们已经提到了，用一个含100个元素的最小堆完成。复杂度为O(100w*lg100)。
方案2：冒泡排序， 冒出前100个。复杂度为O(100w*100)。
1. 算法如下：根据快速排序划分的思想 (1) 递归对所有数据分成[a,b）b（b,d]两个区间，(b,d]区间内的数都是大于[a,b)区间内的数 (2) 对(b,d]重复(1)操作，直到最右边的区间个数小于100个。注意[a,b)区间不用划分 (3) 返回上一个区间，并返回此区间的数字数目。接着方法仍然是对上一区间的左边进行划分，分为[a2,b2）b2（b2,d2]两个区间，取（b2,d2]区间。如果个数不够，继续(3)操作，如果个数超过100的就重复1操作，直到最后右边只有100个数为止。
2. 先取出前100个数，维护一个100个数的最小堆，遍历一遍剩余的元素，在此过程中维护堆就可以了。具体步骤如下： step1：取前m个元素（例如m=100），建立一个小顶堆。保持一个小顶堆得性质的步骤，运行时间为O（lgm);建立一个小顶堆运行时间为m*O（lgm）=O(m lgm); step2:顺序读取后续元素，直到结束。每次读取一个元素，如果该元素比堆顶元素小，直接丢弃 如果大于堆顶元素，则用该元素替换堆顶元素，然后保持最小堆性质。最坏情况是每次都需要替换掉堆顶的最小元素，因此需要维护堆的代价为(N-m)*O(lgm); 最后这个堆中的元素就是前最大的10W个。时间复杂度为O(N lgm）。
3. 分块查找 先把100w个数分成100份，每份1w个数。先分别找出每1w个数里面的最大的数，然后比较。找出100个最大的数中的最大的数和最小的数，取最大数的这组的第二大的数，与最小的数比较。。。。从N个数中查找最小的前K个数，最常规的办法就是进行全排序，所有取前K个最小的即可，但是这样做的话，效率是比较低下的，很有可能过不了。
总结：而题目中要求取的是前k个最小的数，那么我们可以采用最小堆排序，每次调整完堆，堆顶都是本次调整的堆中最小的数，因此只需要调整K次就可以得到最终答案了。
同样，如果是取最大的K个数，就采用最大堆排序就可以了！
