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

top-down还是o(nlgn)。自己没有细想，不过查了一下，发现还是有o(n)的，用的是bottom-up. 

The bottom-up approach enables us to access the list in its order while creating nodes. Each time you are stucked with the top-down approach, give bottom-up a try. Although bottom-up approach is not the most natural way we think, it is extremely helpful in some cases. However, you should prefer top-down instead of bottom-up in general, since the latter is more difficult to verify in correctness.

top down:

1 class Solution { 2 public: 3     TreeNode *sortedListToBST(ListNode *head) { 4         if (head == NULL) return NULL; 5         ListNode* slow = head, *fast = head, *pre = NULL; 6         while(slow != NULL && fast != NULL && fast->next != NULL) { 7             pre = slow; 8             slow = slow->next; 9             fast = fast->next->next;10         }11         12         TreeNode* root = new TreeNode(slow->val);13         14         TreeNode* left = NULL;15         if (pre != NULL) {16             pre->next = NULL;17             left = sortedListToBST(head);18         } 19         20         TreeNode* right = sortedListToBST(slow->next);21         22         root->left = left;23         root->right = right;24         25         return root;26     }27 };

bottom up:

1 class Solution { 2 public: 3     TreeNode *sortedListToBST(ListNode *head) { 4         int n = 0;  5         ListNode* p = head; 6         while (p != NULL) { 7             n++; 8             p = p->next; 9         }10         return recursive(head, 0, n - 1);11     }12     13     TreeNode* recursive(ListNode* &head, int start, int end) {14         if (head == NULL) return NULL;15         if (start > end) return NULL;16         int mid = start + (end - start) / 2;17         TreeNode* left = recursive(head, start, mid - 1);18         TreeNode* root = new TreeNode(head->val);19         head = head->next;20         TreeNode* right = recursive(head, mid + 1, end);21         root->left = left;22         root->right = right;23         return root;24     }25 };

首先是要得到整个list的长度，有了这个长度才能知道最终的BST是什么样子的。然后是先用左边的元素完成左边的子树构建，要确保构建完之后，list的head指针必须更新到末尾。所以这里需要传引用,ListNode*&。整个算法复杂度为o(n)。

另一种做法：

既然知道长度之后就知道最终的BST是什么样子的，那么可以先构建一颗空树。然后inorder traversal填进去就可以。