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.

struct TreeNode {

      int val;

      TreeNode *left;

      TreeNode *right;

      TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};



struct ListNode {

    int val;

    ListNode *next;

    ListNode(int x) : val(x), next(NULL) {}

};







TreeNode* getnode(int x)

{

    TreeNode* t = (TreeNode *)malloc(sizeof(TreeNode));

    t->val = x;

    t->left = NULL;

    t->right =NULL;

    return t;

}





int count(ListNode *root)

{

    int cnt = 0;

    while(root)

    {

        root = root->next;

        cnt++;

    }

    

    return cnt;

}



TreeNode* getmid(ListNode *head, int n)

{

    if(n <= 0)

        return NULL;

    

ListNode * firstHalf;

    ListNode * secondHalf;

    int leftcount;

    int rightcount;

    firstHalf = NULL;

    secondHalf = NULL;

    leftcount = 0;

    rightcount = 0;

    if(n <= 0)

      return NULL;

    

    if(n <= 1)

      return getnode(head->val);

    

    int midindex  = (n % 2 == 0 ? n / 2 : n/ 2 + 1);

    leftcount = midindex - 1;

    rightcount = n - midindex;

    firstHalf = head;    

    ListNode *midNode =  head; 

    while (midindex-- > 0) {

        midNode = head;

        head  = head->next;

    }

    secondHalf = head;

    TreeNode* root = getnode(midNode->val);

    root->left = getmid(firstHalf, leftcount);

    root->right = getmid(secondHalf, rightcount);

    return root;

}

TreeNode *sortedListToBST(ListNode *head) {

   if(!head)

        return NULL;

    int cnt  = count(head);

    return getmid(head, cnt);

}