import java.util.*;
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode mergeKLists(ArrayList<ListNode> lists) {
if(lists.size() == 0){
return null;
}
return mergeRange(lists, 0, lists.size()-1);
}
private static ListNode mergeRange(ArrayList<ListNode> lists, int start, int end){
//起始和结束位置相同,直接返回。
if(start == end){
return lists.get(start);
}
int mid = (start + end) / 2;
return merge(mergeRange(lists, start, mid), mergeRange(lists, mid + 1, end));
}
private static ListNode merge(ListNode list1, ListNode list2){
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while(list1 != null && list2 != null){
if(list1.val < list2.val){
cur.next = list1;
cur = cur.next;
list1 = list1.next;
}else{
cur.next = list2;
cur = cur.next;
list2 = list2.next;
}
}
if(list1 != null){
cur.next = list1;
}
if(list2 != null){
cur.next = list2;
}
return dummy.next;
}
}
#学习##刷题##每日刷题#