[Leetcode] 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.

Analysis:

class Solution {
public:

    TreeNode *sortedListToBST(ListNode *head) {
        if (head == NULL)
            return NULL;
        
        if (head->next == NULL)
            return new TreeNode(head->val);
        
        //use fast and slow pointer to get the middle
        ListNode* fast = head;
        ListNode* slow = head;
        ListNode* prev = NULL;
        while(fast != NULL && fast->next != NULL)
        {
            prev = slow;
            fast = fast->next->next;
            slow = slow->next;
        }
        //divide the list into two part
        prev->next = NULL;
        //middle as the root
        TreeNode* root = new TreeNode(slow->val);
        //recursively convert the left and right node
        root->left = sortedListToBST(head);
        root->right = sortedListToBST(slow->next);
        return root;
    }
};