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.


--------------------------------- codes -----------------------------------------------------
/**
 * 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 *sortedListToBST(ListNode *head) {
        if (head == NULL) {
            return NULL;
        }
        if (!head->next) {
            TreeNode *ele = new TreeNode(head->val);
            return ele;
        }
        pair<ListNode*, ListNode*> m = findMedium(head);
        m.first->next = NULL;
        ListNode* right = m.second->next;
        TreeNode *ele = new TreeNode(m.second->val);
        ele->left = sortedListToBST(head);
        ele->right = sortedListToBST(right);
        return ele;
    }

    pair<ListNode*, ListNode*> findMedium(ListNode *head) {
        assert(head->next);
        ListNode* medium;
        ListNode* pre;
        ListNode* fast;
        fast = head->next->next;
        medium = head;
        while (fast && fast->next) {
            fast = fast->next->next;
            medium = medium->next;
        }
        pre = medium;
        medium = medium->next;
        return make_pair(pre, medium);
    }
};