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.

 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
	private ListNode h;
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
        	return null;
        }
        h = head;
        ListNode tmp = head;
        int cnt = 0;
        while (tmp != null) {
        	cnt++;
        	tmp = tmp.next;
        }
        return solve(0, cnt-1);
    }
	private TreeNode solve(int s, int e) {
		if (s > e) {
			return null;
		}
		int mid = (s+e)/2;
		TreeNode left = solve(s, mid-1);
		TreeNode root = new TreeNode(h.val);
		root.left = left;
		h = h.next;
		TreeNode right = solve(mid+1, e);
		root.right = right;
		return root;
	}
}