02
Intuition
Balance demands the middle element as root. Finding the middle of a list repeatedly costs O(n log n) — instead, build inorder: recurse on sizes, consume list nodes left-to-right exactly when the inorder traversal would visit them. The list pointer advances once per node, total O(n).
03
Approach
1
Sizes first
Count the list length n. build(l, r) constructs the subtree covering positions l..r without knowing values in advance.
2
Inorder consumption
Build the left subtree, THEN take the current list node as root (advance the pointer), then build the right — values arrive in exactly the right order.
3
Balanced by construction
Midpoint split of sizes guarantees height ⌈log n⌉.
04
Solution & live demo
python
▶1class Solution:
▶2 def sortedListToBST(self, head):
▶3 n, cur = 0, head
▶4 while cur: n += 1; cur = cur.next
▶5 self.cur = head
▶6 def build(l, r):
▶7 if l > r: return None
▶8 mid = (l + r) // 2
▶9 left = build(l, mid - 1)
▶10 node = TreeNode(self.cur.val) # inorder moment
▶11 self.cur = self.cur.next
▶12 node.left = left
▶13 node.right = build(mid + 1, r)
▶14 return node
▶15 return build(0, n - 1)
05
Edge cases
Empty list
n=0 → None.
Even length
Either middle works; mid = (l+r)//2 picks consistently.
06
Complexity
Time
O(n)
Space
O(log n)
List consumed strictly in order.