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)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 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; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 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); } };