Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

每次二分法找中点，此点为root，左半部分为左子树，右半部分为右子树。

public class Solution {
    //Time: O(nlogn)
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        
        if (head.next == null || head.next.next == null) {
            TreeNode root = new TreeNode(head.val);
            if (head.next != null) {
                root.right = new TreeNode(head.next.val);
            }
            return root;
        }
        
        ListNode midPre = findMidPre(head);
        ListNode mid = midPre.next;
        TreeNode root = new TreeNode(mid.val);
        midPre.next = null;
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(mid.next);
        return root;
    }
    
    private ListNode findMidPre(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;
        
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}