题目描述： Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
读题： 合并若干个有序列表
知识储备： 归并排序 将待排序序列R[0…n-1]看成是n个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序序列再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列
归并排序其实要做两件事： （1）“分解”——将序列每次折半划分。 （2）“合并”——将划分后的序列段两两合并后排序。
时间复杂度 归并排序的形式就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的可以得出它的时间复杂度是O(n*log2n)。
空间复杂度 需要一个大小为n的临时存储空间用以保存合并序列。
解题思路： 类似归并排序， （1）“分解”——将链表数组每次折半划分。 （2）“合并”——将划分后的链表两两合并排序。
时间复杂度 它需要遍历的次数就是二叉树的深度，而根据完全二叉树的可以得出它的时间复杂度是O(n*log2n)。
空间复杂度 排序时只需改变链表的指针指向即可，不需要一个新的数组。因此空间复杂度为O（1）
提交代码：
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode mergeKLists(ListNode[] lists) { int len = lists.length; if (len == 0) { return null; } else if (len == 1) { return lists[0]; } int mid = len / 2; //划分链表数组 ListNode left = mergeKLists(Arrays.copyOfRange(lists, 0, mid)); ListNode right = mergeKLists(Arrays.copyOfRange(lists, mid,len)); return mergeTwoLists(left, right); } //两两链表合并 public ListNode mergeTwoLists(ListNode a , ListNode b){ ListNode res = new ListNode(0) ; ListNode cur = res; while(a != null && b != null){ if(a.val < b.val){ cur.next = a ; a = a.next ; }else{ cur.next = b ; b = b.next ; } cur = cur.next ; } while(a != null){ cur.next = a ; a = a.next ; cur = cur.next ; } while(b != null){ cur.next = b ; b = b.next ; cur = cur.next ; } return res.next ; } }