/**
 * 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;
        int len = 0;
        ListNode curr = head;
        while (curr != null) {
            curr = curr.next;
            len++;
        }
        return recursion(head, 0, len - 1);
    }
    
    private TreeNode recursion(ListNode head, int lo, int hi) {
        if (lo > hi)
            return null;
        int mid = lo + (hi - lo) / 2;
        int count = 0;
        ListNode curr = head;
        while (count < mid) {
            count++;
            curr = curr.next;
        }
        TreeNode node = new TreeNode(curr.val);
        node.left = recursion(head, 0, mid - 1);
        node.right = recursion(curr.next, 0, hi - mid - 1);
        return node;
    }
    
}