Merge k Sorted Lists leetcode

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
用分治法的mergesort的思想 把lists分成小list 最后合并
merge的方法就是之前merge 2 sorted list的方法

时间复杂度O(nlog(n)) 计算方法用主定理

/**
 * 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) {
  
        if (lists.length == 0 || lists == null){
            return null;
        }
        return sort(lists, 0, lists.length - 1);
    }
    private ListNode sort(ListNode[] lists, int start, int end){
        if (start == end){
            return lists[start];
        }
        int mid = (start + end) / 2;
        ListNode left = sort(lists, start, mid);
        ListNode right = sort(lists, mid + 1, end);
        return merge(left, right);
    }
    private ListNode merge(ListNode left, ListNode right){
        ListNode dummy = new ListNode(0);
        ListNode point = dummy;
        while (left != null && right != null){
            if (left.val < right.val){
                point.next = left;
                left = left.next;
            } else {
                point.next = right;
                right = right.next;
            }
            point = point.next;
        }
        if (left != null){
            point.next = left;
        } else {
            point.next = right;
        }
        return dummy.next;
    }
}