题目描述：
合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。
范围：
节点总数>=0 、链表个数 >= 1 、 链表长度 >= 1
示例1：
输入：[{1,2,3},{4,5,6,7}]
返回值：{1,2,3,4,5,6,7}
示例2：
输入：[{1,2},{1,4,5},{6}]
返回值：{1,1,2,4,5,6}
初始代码：
import java.util.*; public class Solution { public ListNode mergeKLists(ArrayList<ListNode> lists) { } }
解决思路：
1、先写一个功能函数merge，能够将两个有序链表合并成一个有序链表
2、按照顺序 一个个合并每一个链表！
失误点：时间复杂度过高！代码运算超时！
如何解决： 利用归并的思想！
- step 1：从链表数组的首和尾开始，每次划分从中间开始划分，划分成两半，得到左边n/2个链表和右边n/2个链表。
- step 2：继续不断递归划分，直到每部分链表数为1.
- step 3：将划分好的相邻两部分链表，按照两个链表合并的方式合并，合并好的两部分继续往上合并，直到最终合并成一个链表。
import java.util.*; public class Solution { private ListNode merge(ListNode list1, ListNode list2) { if (list1 == null && list2 == null) { return null; } else if (list1 != null && list2 == null) { return list1; } else if (list1 == null) { return list2; } ListNode ret = new ListNode(0); ListNode cur = ret; while (list1 != null && list2 != null) { if (list1.val <= list2.val) { ListNode node = new ListNode(list1.val); cur.next = node; list1 = list1.next; } else { ListNode node = new ListNode(list2.val); cur.next = node; list2 = list2.next; } cur = cur.next; } if (list1 == null) { cur.next = list2; } else { cur.next = list1; } return ret.next; } //！！时间超时的原本代码 // public ListNode mergeKLists(ArrayList<ListNode> lists) { // if (lists.isEmpty()){ // return null; // } // ListNode[] arr = new ListNode[lists.size()]; // lists.toArray(arr); // int index = arr.length; // ListNode ret = merge(arr[index-1],arr[index-2]); // index-=3; // while(index>=0){ // ret=merge(ret,arr[index]); // index--; // } // return ret; // } //下面是改进后的代码 public ListNode mergeKLists(ArrayList<ListNode> lists) { ListNode[] arr = new ListNode[lists.size()]; lists.toArray(arr); return merge1(arr, 0, arr.length - 1); } private ListNode merge1(ListNode[] arr, int left, int right) { if (left>right){ return null; }else if (left==right){ return arr[left]; } int mid = (left+right)/2; //重点要读懂这一句！！ return merge(merge1(arr,left,mid),merge1(arr,mid+1,right)); } }
