import java.util.ArrayList;
import java.util.List;

public class _109 {
    static class Solution {
        public TreeNode sortedListToBST(ListNode head) {
            List<ListNode> arr = new ArrayList<>();
            while (head != null) {
                arr.add(head);
                head = head.next;
            }
            int[] nums = new int[arr.size()];
            int i = 0;
            for (ListNode val : arr) {
                nums[i++] = val.val;
            }
            return build(nums, 0, nums.length - 1);
        }

        public TreeNode build(int[] nums, int l, int r) {
            if (l > r) return null;
            int mid = l + (r - l) / 2;
            TreeNode root = new TreeNode(nums[mid]);
            root.left = build(nums, l, mid - 1);
            root.right = build(nums, mid + 1, r);
            return root;
        }
    }
}