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.
Note:
Things get a little more complicated when you have a singly linked list instead of an array. Please note that in linked list, you no longer have random access to an element in O(1) time.
Naive Solution:
A naive way is to apply the previous solution directly. In each recursive call, you would have to traverse half of the list’s length to find the middle element. The run time complexity is clearly O(N lg N), where N is the total number of elements in the list. This is because each level of recursive call requires a total of N/2 traversal steps in the list, and there are a total of lg N number of levels (ie, the height of the balanced tree).
Best Solution:
We no longer create nodes in the tree using the top-down approach. We create nodes bottom-up, and assign them to its parents. The bottom-up approach enables us to access the list in its order while creating nodes.
The algorithm requires the list’s length to be passed in as the function’s parameters. 
对于一个链表我们是不能常量时间访问它的中间元素的。这时候就要利用到树的中序遍历了，按照递归中序遍历的顺序对链表结点一个个进行访问，而我们要构造的二分查找树正是按照链表的顺序来的。思路就是先对左子树进行递归，然后将当前结点作为根，迭代到下一个链表结点，最后在递归求出右子树即可。
The list’s length could be found in O(N) time by traversing the entire list’s once. The recursive calls traverse the list and create tree’s nodes by the list’s order, which also takes O(N) time. Therefore, the overall run time complexity is still O(N). 空间复杂度是栈空间O(logn) .

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; next = null; }
 * }
 */
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null)
            return null;
        
        ListNode cur = head;
        int count = 0;
        while(cur != null) {
            cur = cur.next;
            count++;
        }
        
        ArrayList list = new ArrayList();
        list.add(head);
        return sortHelper(0, count - 1, list);
    }
    
    // build bottom-up
    public TreeNode sortHelper(int start, int end, ArrayList list) {
        if(start > end)  //if finished, get the root
            return null;
        
        int mid = (start + end) / 2; //find the mid element
        
        TreeNode left = sortHelper(start, mid - 1, list);  //build left subtree
        TreeNode root = new TreeNode(list.get(0).val); //build root node
        root.left = left;  //assign left to the left subtree
        list.set(0,list.get(0).next);  //pointer +1
        TreeNode right = sortHelper(mid + 1, end, list);  //move to next node to build right subtree
        root.right = right;  //assign right to the right subtree
        return root;
    }
}