题目：
思路：
解法用了三种：
1，采用搭建小顶堆的方式通过把节点塞入堆内自动排序，然后取出最小值，直至堆内为空，元素加入堆中的时间复杂度为O（longk），总共有kn个元素加入堆中，因此，时间复杂度是O（nklogk），空间复杂度的话是O（K），因为堆内存放数据量是根据有多少个链表来的
2，链表1、2合并，然后其结果12和3合并，以此类推，最后是123--k-1和k合并。假设每个链表的平均长度是n，则1、2合并，遍历2n个节点；12结果和3合并，遍历3n个节点；....123...k-1的结果和k合并，遍历kn个节点，总共遍历n(2 3 4 ....k)=n*(k^2 k-2)/2。
这种方法的时间复杂度是O(n*(k^2 k-2)/2)=O(nk^2)。
3，是使用归并思路，先两两将小的链表合并成更大一点的链表，然后将更大的链表再合并。
下面是提交的结果，第一次是小顶堆的方案，第二次是暴力拼接的方案，第三次是归并思路的方案
代码示例：
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
public class Solution {
public static void main(String[] args) {
ListNode arr1 = new ListNode(1);
ListNode end1 = arr1;
ListNode temp1 = arr1;
ListNode arr2 = new ListNode(4);
ListNode end2 = arr2;
ListNode temp2 = arr2;
ListNode arr3 = new ListNode(9);
ListNode end3 = arr3;
ListNode temp3 = arr3;
ListNode arr4 = new ListNode(17);
ListNode end4 = arr4;
ListNode temp4 = arr4;
ArrayList<ListNode> lists = new ArrayList<ListNode>();
for (int i = 2; i < 4; i ) {
ListNode temp = new ListNode(i);
temp1.next = temp;
temp1 = temp;
}
OutPutLinkedList(end1);
for (int i = 5; i < 8; i ) {
ListNode temp = new ListNode(i);
temp2.next = temp;
temp2 = temp;
}
OutPutLinkedList(end2);
for (int i = 10; i < 16; i ) {
ListNode temp = new ListNode(i);
temp3.next = temp;
temp3 = temp;
}
OutPutLinkedList(end3);
for (int i = 18; i < 25; i ) {
ListNode temp = new ListNode(i);
temp4.next = temp;
temp4 = temp;
}
OutPutLinkedList(end4);
lists.add(null);
lists.add(null);
// lists.add(arr1);
// lists.add(arr2);
// lists.add(arr3);
// lists.add(arr4);
ListNode result = mergeKLists(lists);
OutPutLinkedList(result);
}
/**
* 利用归并的思想将两个小的先行组合成一个大的，如【0,1,2,3,4,5】六条，0与3先排序，1与4,2与5,
* 然后形成新的【0,1,2】，再0与2排序，最后把1也合并了。
*
* @param lists
* @return
*/
public static ListNode mergeKLists(ArrayList<ListNode> lists) {
int len = lists.size();
if (lists.size() == 0)
return null;
while (len > 1) {
int k = (len 1) >> 1;
for (int i = 0; i < len / 2; i ) {
lists.set(i, mergeTwo(lists.get(i), lists.get(i k)));
}
len = k;
}
return lists.get(0);
}
/**
* 使用暴力的方法把每一条都加进去合并成为一条
*
* @param lists
* @return
*/
public static ListNode mergeKLists2(ArrayList<ListNode> lists) {
if (lists.size() == 0)
return null;
if (lists.size() == 1)
return lists.get(0);
ListNode result = lists.get(0);
for (int i = 1; i < lists.size(); i ) {
result = mergeTwo(result, lists.get(i));
}
return result;
}
/**
* 将两个有序链表进行合并
*
* @param head1
* @param head2
* @return
*/
public static ListNode mergeTwo(ListNode head1, ListNode head2) {
if (head1 == null)
return head2;
if (head2 == null)
return head1;
ListNode new_list = new ListNode(0);
ListNode temp = new_list;
while (head1 != null || head2 != null) {
if (head1 != null && head2 != null) {
if (head1.val < head2.val) {
temp.next = head1;
head1 = head1.next;
} else {
temp.next = head2;
head2 = head2.next;
}
} else if (head1 != null) {
temp.next = head1;
head1 = head1.next;
} else if (head2 != null) {
temp.next = head2;
head2 = head2.next;
}
temp = temp.next;
}
//为什么返回的是下一个节点？原因在于，在上面创建了一个新的节点，而新的节点后面的才是将两个链表合并排序的东西
//所以你要把自己创建的那个节点给清除掉
return new_list.next;
}
/**
* 利用小顶堆思想的合并多个已排序链表
*
* @param lists
* @return
*/
public static ListNode mergeKLists1(ArrayList<ListNode> lists) {
ListNode result = new ListNode(0);
ListNode temp = result;
//优先队列，即堆，使用小顶堆
PriorityQueue<ListNode> nodeHeap = new PriorityQueue<>(new Comparator<ListNode>() {
@Override
public int compare(ListNode o1, ListNode o2) {
return o1.val - o2.val;
}
});
//将链表的投节点添加到小顶堆中
for (ListNode h : lists) {
if (null != h) {
nodeHeap.add(h);
}
}
//从堆中拿出元素链表接到结果链表中，并查看该链表是否有下一节点，有的话将下一节点加入堆中，重复操作直至所有堆清空
while (!nodeHeap.isEmpty()) {
ListNode node = nodeHeap.poll();
temp.next = node;
temp = node;
if (null != node.next) {
nodeHeap.add(node.next);
}
}
return result.next;
}
/**
* 打印链表，用于输出查看
*
* @param head
*/
public static void OutPutLinkedList(ListNode head) {
ListNode temp = head;
while (null != temp) {
System.out.print(temp.val);
if (null != temp.next) {
System.out.print(" -> ");
}
temp = temp.next;
}
System.out.println();
}
}
