Sorted Link List to BST

Given a Singly Linked List which has data members sorted in ascending order. Construct a Balanced Binary Search Tree which has same data members as the given Linked List.

Note: There might be nodes with same value.

• Time : O(nlogn)
• Space : O(logn)

c++

/* 
//Linked List
struct LNode
{
    int data;
    struct LNode* next;
    
    LNode(int x){
        data = x;
        next = NULL;
    }
};

//Tree
struct TNode  
{  
    
    int data;  
    struct TNode* left;  
    struct TNode* right; 
    TNode(int x)
    {
        data=x;
        left=right=NULL;
    }
}; */
class Solution{
public:
    TNode* sortedListToBST(LNode *head) {
        if(head == nullptr) return nullptr;
        if(head->next == nullptr) return new TNode(head->data);
        
        LNode *slow = head, *fast = head;
        while(fast->next->next and fast->next->next->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        
        LNode* mid = slow->next;
        LNode* right = mid->next;
        
        slow->next = nullptr;
        mid->next = nullptr;
        
        TNode* root = new TNode(mid->data);
        root->left = sortedListToBST(head);
        root->right = sortedListToBST(right);
        
        return root;
    }
};

• Time : O(n)
• Space : O(n)

c++

class Solution{
    int count(LNode* head) {
        LNode* runner = head;
        int c = 0;
        while(head) {
            c++;
            head = head->next;
        }
        return c;
    }
    TNode* dnc(LNode **head, int n) {
        if(n <= 0) return 0;
        TNode* left = dnc(head, n / 2);
        TNode* root = new TNode((*head)->data);
        (*head) = (*head)->next;
        TNode* right = dnc(head, n - n / 2 - 1);
        root->left = left;
        root->right = right;
        return root;
    }
  public:
    TNode* sortedListToBST(LNode *head) {
        if(!head) return nullptr;
        int c = count(head);
        return dnc(&head, c);
    }
};