109. 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.
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.
Example:
Given the sorted linked list: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5
---
Intuition
Find the mid point of list using fast, slow pointers
mid element of list is root of tree

set the prev to mid to null
head to prev is first half - left child .. recurse
mid.next is second half - right child ..recurse

* base case of recursion is when head == mid .. only one element in the list
---
Time - O( log N) - we divide the list log N times till 1 element
Space - O( log N) - recursion call stack
---
Related problems
convert-sorted-array-to-binary
balance-binary-search-tree