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

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

&nbsp;
Example 1:

Input: head = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: One possible answer is [0,-3,9,-10,null,5], which represents the shown height balanced BST.


Example 2:

Input: head = []
Output: []


&nbsp;
Constraints:


	The number of nodes in head is in the range [0, 2 * 104].
	-105 &lt;= Node.val &lt;= 105


class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        arr = []
        while head:
            arr.append(head.val)
            head = head.next
        def dfs(left, right):
            if left > right: return
            m = (left + right)//2
            return TreeNode(arr[m], dfs(left, m-1), dfs(m+1, right))
        return dfs(0, len(arr)-1)
class Solution {
    
        public TreeNode sortedListToBST(ListNode head) {
            
            ListNode tmp = head;
            ArrayList<Integer> treelist = new ArrayList<>();
            
            while(tmp != null) {
                treelist.add(tmp.val);
                tmp = tmp.next;
            }
            
            return createTree(treelist, 0, treelist.size()-1);
        }
    
        public TreeNode createTree(ArrayList<Integer> treelist, int start, int end) {
            
            if(start > end)
                return null;
            
            int mid = start + (end-start)/2;
            
            TreeNode node = new TreeNode(treelist.get(mid));//getNode(treelist.get(mid));
            
            node.left = createTree(treelist, start, mid-1);
            node.right = createTree(treelist, mid+1, end);
            return node;
        }
}
class Solution {
public:
    typedef vector<int>::iterator vecIt;
    TreeNode* buildTree(vector<int>& listToVec, vecIt start, vecIt end)
    {
        if (start >= end)
            return NULL;
        vecIt midIt = start + (end - start) / 2;
        TreeNode* newNode = new TreeNode(*midIt);
        newNode->left = buildTree(listToVec, start, midIt);
        newNode->right = buildTree(listToVec, midIt + 1, end);
        return (newNode);
    }
    TreeNode* sortedListToBST(ListNode* head) {
        vector<int> listToVec;
        while (head)
        {
            listToVec.push_back(head->val);
            head = head->next;
        }
        return (buildTree(listToVec, listToVec.begin(), listToVec.end()));
    }
};
var sortedListToBST = function(head) {
    if(!head) return null;
    if(!head.next) return new TreeNode(head.val);
    
    let fast = head, slow = head, prev = head;
    while(fast && fast.next) {
        prev = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    
    const root = new TreeNode(slow.val);
    prev.next = null;
    
    const newHead = slow.next;
    slow.next = null;
    
    root.left = sortedListToBST(head);
    root.right = sortedListToBST(newHead);
    
    return root;
};
Convert Sorted List to Binary Search Tree