case1:逐一两两合并

class Solution {public ListNode twoWayCombation(ListNode h1,ListNode h2){//二路归并if(h1==null&&h2==null)return h1;if(h1==null)return h2;if(h2==null)return h1;ListNode head = new ListNode(-1);ListNode rear = head;while(h1!=null&&h2!=null){if(h1.val<=h2.val){rear.next = h1;h1 = h1.next;}else{rear.next = h2;h2 = h2.next;}rear = rear.next;}if(h1!=null){rear.next = h1;}if(h2!=null){rear.next = h2;}return head.next;}public ListNode mergeKLists(ListNode[] lists) {int len = lists.length;if(len<=0)return null;if(len==1)return lists[0];ListNode left = lists[0];int right = 1;while(right<len){left = twoWayCombation(left,lists[right]);right++;}return left;}
}

case2:思想：采用外部排序，利用小顶堆来实现
时间复杂度O( n*logk) 空间复杂度O(k) k为链表的个数，n为链表的最大长度

class Solution {public ListNode mergeKLists(ListNode[] lists) {if(lists.length==1) return lists[0];PriorityQueue<ListNode> heap = new PriorityQueue<>(new Comparator<ListNode>(){@Overridepublic int compare(ListNode o1,ListNode o2){return o1.val-o2.val;}});for(ListNode head:lists){if(head!=null){heap.add(head);}}ListNode newHead = new ListNode(-1);ListNode rear = newHead;while(!heap.isEmpty()){ListNode cur = heap.poll();ListNode next = cur.next;if(next!=null){heap.add(next);}cur.next = null;rear.next = cur;rear = rear.next;  }return newHead.next;}
}

case3：使用分治思想，对链表使用二路归并排序
时间复杂度O(nlog k ),空间复杂度O(logk)

class Solution {public ListNode merge(ListNode h1,ListNode h2){if(h1==null&&h2==null)return h1;if(h1==null)return h2;if(h2==null)return h1;ListNode head = new ListNode(-1);ListNode rear = head;while(h1!=null&&h2!=null){if(h1.val<=h2.val){rear.next = h1;h1 = h1.next;}else{rear.next = h2;h2 = h2.next;}rear = rear.next;}if(h1!=null){rear.next = h1;}if(h2!=null){rear.next = h2;}return head.next;}public ListNode dividen(ListNode[]lists,int start,int end){if(start>end) return null;if(start==end) return lists[start];int mid = (start+end)/2;ListNode left = dividen(lists,start,mid);ListNode right = dividen(lists,mid+1,end);return merge(left,right);}public ListNode mergeKLists(ListNode[] lists) {int len = lists.length;if(len<=0)return null;if(len==1)return lists[0];return dividen(lists,0,len-1);}
}