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

Solution：Recusive 选中点 并左右递归建立

思路：快慢指针找到中点后，左右递归建立
递归input: start, end; return: 建好的头结点

Time Complexity: O(n logn) Space Complexity: O(logN) 递归缓存

Solution1 Code：

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null) return null;
        return toBST(head, null);
    }
    public TreeNode toBST(ListNode head, ListNode tail){
        if(head == tail) return null;
        
        // use slow to find mid, 
        ListNode slow = head;
        ListNode fast = head;
        while(fast != tail && fast.next != tail){
            fast = fast.next.next;
            slow = slow.next;
        }
        
        // recursively build
        TreeNode node = new TreeNode(slow.val);
        node.left = toBST(head, slow);
        node.right = toBST(slow.next, tail);
        
        return node;
    }
}