109. Convert Sorted List to Binary Search Tree
You are given the head of a singly linked list whose values are distinct and sorted in strictly increasing order. Build a height-balanced binary search tree containing the same values — at every node, the two subtree heights may differ by at most one — and return its root.
The list is the inorder sequence of the target BST, so the move is the same as with a sorted array — root the middle, recurse on both sides — except a linked list offers no O(1) jump to its middle, which is what makes this version interesting.
Canonical form (so exactly one answer is correct): whenever a stretch of the list holds an even number of nodes, root that stretch at the left of its two middle nodes.
An empty list becomes an empty tree. The judge prints your tree in level order with null marking a missing child of a present node, dropping trailing null markers.
Example 1:
Input: head = [-10, -3, 0, 5, 9]
Output: [0, -10, 5, null, -3, null, 9]
Explanation: The middle node 0 roots the tree. The two nodes before it, [-10, -3], root at -10 (left middle) with -3 to its right; the two after it, [5, 9], root at 5 with 9 to its right.
Example 2:
Input: head = [1, 2, 3]
Output: [2, 1, 3]
Explanation: Three nodes have a unique middle: 2 becomes the root with 1 and 3 as its children.
Constraints:
- 0 ≤ number of nodes ≤ 2000
- -10⁴ ≤ node value ≤ 10⁴
- The list values are strictly increasing (all distinct).
Hints:
If you could index the values like an array, this would be exactly the sorted-array version: middle becomes the root, halves become the subtrees. What is the cheapest way to buy yourself that indexing?
You can find a list's middle without an array: advance a fast pointer two steps for every one step of a slow pointer, stopping so that the slow pointer lands on the left middle of the stretch you are splitting.
Splitting at the middle rescans half the list at every level (O(n log n)). Flip the construction inorder instead: count the nodes once, recurse on index ranges, build the left subtree first, *then* consume the next list node as the root — the list pointer advances exactly in sorted order, giving O(n).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: head = [-10, -3, 0, 5, 9]
Expected output: [0, -10, 5, null, -3, null, 9]