Cacher is the code snippet organizer for pro developers

// top-down approach, great version!!!

TreeNode* sortedListToBST(ListNode *head) { 
	if(!head) return NULL;
	if(!head->next) return new TreeNode(head->val);
	ListNode *slow = head, *fast = head;
	ListNode *left_tail = slow;
	while(fast && fast->next) {
		left_tail = slow;
		slow = slow->next;
		fast = fast->next->next;
	}
	left_tail->next = NULL;
	
	ListNode *left_half = head, *right_half = slow->next;
	TreeNode *root = new TreeNode(slow->val);
	root->left = sortedListToBST(left_half);
	root->right = sortedListToBST(right_half);
	return root;
} 

// bottom-up approach, hard to think.
TreeNode* sortedListToBST(ListNode *head) { 
    int len = 0;
    ListNode *p = head;
    while(p) {
        len++;
        p = p->next;
    }
    return helper(head, 0, len-1);
}

TreeNode* helper(ListNode* &head, int start, int end) {
    if(start > end) return NULL;
    int m = start + (end - start) / 2;
    TreeNode *left_half = helper(head, start, m-1);
    TreeNode *root = new TreeNode(head->val);
    root->left = left_half;
    head = head->next;
    root->right = helper(head, m+1, end);
    return root;
}