Convert a sorted singly linked list into a height-balanced binary search tree.
Given the head of a singly linked list whose values are sorted in non-decreasing order, build a height-balanced binary search tree containing the same values.
A binary search tree is valid if for every node, all values in its left subtree are smaller than the node value and all values in its right subtree are larger. The tree should also be height-balanced, meaning the depths of the two subtrees of every node differ by at most one.
Return any valid height-balanced BST that uses all list nodes exactly once.
Input Format
- A singly linked list head node representing values in non-decreasing order.
- Each list node contains one integer value.
Output Format
- Return the root of a height-balanced binary search tree built from the list values.
Constraints
- The input list is sorted in non-decreasing order.
- All list nodes must be used exactly once.
- The resulting tree must be height-balanced.
- If the list is empty, return null.
Example 1
Input
head = [-10, -3, 0, 5, 9]
Output
[0, -3, 9, -10, null, 5]
Explanation
One valid height-balanced BST is rooted at 0, with -3 on the left and 9 on the right. The exact shape may vary as long as the BST property and balance condition hold.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.