# Convert Sorted List to Binary Search Tree LeetCode Solution Share:

Convert Sorted List to Binary Search Tree Given the `head` of a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example 1:

```Input: head = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: One possible answer is [0,-3,9,-10,null,5], which represents the shown height balanced BST.
```

Example 2:

```Input: head = []
Output: []
```

Constraints:

• The number of nodes in `head` is in the range `[0, 2 * 104]`.
• `-105 <= Node.val <= 105`

Time: O(n log n)
Space: O(log n)

### C++

``````class Solution {
public:
return nullptr;

TreeNode* root = new TreeNode(mid->val);
root->right = sortedListToBST(mid->next);

return root;
}

private:
ListNode* prev = nullptr;

while (fast && fast->next) {
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
prev->next = nullptr;

return slow;
}
};
``````

### Java

`````` class Solution {
return null;

TreeNode root = new TreeNode(mid.val);
root.right = sortedListToBST(mid.next);

return root;
}

ListNode prev = null;

while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
prev.next = null;

return slow;
}
}
``````

### Python

``````
class Solution:
def sortedListToBST(self, head: ListNode) -> TreeNode:
prev = None

while fast and fast.next:
prev = slow
slow = slow.next
fast = fast.next.next
prev.next = None

return slow

return None