Convert_sorted_list_to_binary_search_tree

/*
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.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *helper(ListNode *&head,int start, int end)
    {
      if (start>end) return NULL;
      int mid=(start+end)/2;
      TreeNode *leftTree=helper(head,start,mid-1);
      TreeNode *root = new TreeNode(head->val);
      head=head->next;
      TreeNode *rightTree=helper(head,mid+1,end);
      root->left=leftTree;
      root->right=rightTree;
      return root;
    }

    TreeNode *sortedListToBST(ListNode *head) {
      if(head==NULL) return NULL;
      //get the length of the linked list
      ListNode *h=head;
      int len=0;
      while(h)
      {
	h=h->next;
	len++;
      }
      return helper(head,1,len);
    }
};

REMARK:
1.SUPER HARD. Hard to explain the idea, better read the code after reading the explanation below.
Naive Solution:
A naive way is to apply the previous solution(Convert sorted array to binary search tree) directly. In each recursive call, you would have to traverse half of the list’s length to find the middle element. The run time complexity is clearly O(N lg N), where N is the total number of elements in the list. This is because each level of recursive call requires a total of N/2 traversal steps in the list, and there are a total of lg N number of levels (ie, the height of the balanced tree).

However For the list data structure, to get the mid point every time is a waster of time.

So construct the BST in a bottom-up way. However, the length of the list must be computed.
Recursively 
1. construct the left tree 
2. construct the root node, list pointer +1.
3. construct the right node

2.Note: in the call to helper(head,1,len), the start index is 1(not 0) and the end index is len(not len-1)