题目：
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
看到这道题，能想起来昨天我写的有一篇和这个题有些类似的博客，【合并两个有序的链表】
因此这个题的思路就是
1.k个有序的链表，根据我们之前做的那道题，应该采用两两合并，也就是累加法，最后合并到一起去
2.两个链表的长度可能不一样，我们需要考虑补全的问题。
代码如下：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
ListNode res = new ListNode(0); //设置结果
if(lists == null || lists.length < 0){
return null;
}else if(lists.length == 1){
return lists[0];
}else if(lists.length == 2){
mergeTwoLists(lists[0],lists[1]);
}else{
res = mergeTwoLists(lists[0],lists[1]);
for(int i = 2; i < lists.length;i++){
mergeTwoLists(res,lists[i]);
}
}
return res;
} public ListNode mergeTwoLists(ListNode l1,ListNode l2){
ListNode res = new ListNode(0);
ListNode tmp = res; while(l1 != null && l2 != null){
if(l1.val < l2.val){
tmp.next = l1;
l1 = l1.next;
}else{
tmp.next = l2;
l2 = l2.next;
}
tmp = tmp.next;
}
//后面是为了补全的，因为链表的长度可能不一样
if(l1 != null){
tmp.next = l1;
}else{
tmp.next = l2;
}
return res.next;
}
}
在别的博客中看到另一种解法，就是用优先队列，感觉挺高大上的，所以贴出来和大家分享，只是上面的方法我们容易理解一些罢了。
代码如下：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null || lists.length < 0){
return null;
}
PriorityQueue<Integer> queue = new PriorityQueue();
for(ListNode node:lists){
while(node != null){
queue.add(node.val);
node = node.next;
}
}
ListNode res = new ListNode(0);
ListNode tmp= res;
while(!queue.isEmpty()){
ListNode temp = new ListNode(queue.poll());
tmp.next = temp;
tmp = tmp.next;
}
return res.next;
}
}