1.按照合并两条链表的方法依次合并k条链表
时间复杂度O（n*(k-1)）
/**
* 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.length==1){
return lists[0];
}
if(lists.length==0){
return null;
}
ListNode aim=new ListNode(0);
for(int i=1;i<lists.length;i++){
if(i==1){
aim=merge(lists[0],lists[i]);
}else{
aim=merge(aim,lists[i]);
}
}
return aim;
}
public static ListNode merge(ListNode a,ListNode b){
ListNode head=new ListNode(0);
head.next=a;
ListNode p1=head,p2=a;
ListNode q1,q2=b;
while(p2!=null&&q2!=null){
if(q2.val<p2.val){
q1=q2;
q2=q2.next;
q1.next=p2;
p1.next=q1;
p1=p1.next;
}else{
p1=p1.next;
p2=p2.next;
}
}
if(q2!=null){
p1.next=q2;
}
return head.next;
}
}
2.还有一种方法，直接将所有链表的所有值存进1个数组中，然后进行排序，根据数组中的值重新建立一个链表。
时间复杂度O(nlogn).
