Sorted List to BST
Mahabharata — The Linked Chain to Balanced Formation — Convert Sorted Linked List to BST
सूची में मध्य — slow/fast से ढूँढो। Mid है root — बाकी को विभाजित करो॥
*Middle in the list — find with slow/fast. Mid is root — split the rest.*
The Story
Convert a sorted singly linked list to a height-balanced BST.
For `head=[-10,-3,0,5,9]`: same as tr-34, valid answer `[0,-3,9,-10,null,5]`.
**Challenge:** No random access! Can't do `nums[mid]`. Must find middle of linked list using slow/fast pointer technique.
```java public TreeNode sortedListToBST(ListNode head) { if (head == null) return null; if (head.next == null) return new TreeNode(head.val); // Single node // Find middle using slow/fast ListNode prev = null, slow = head, fast = head; while (fast != null && fast.next != null) { prev = slow; slow = slow.next; fast = fast.next.next; } // slow = middle, prev = node before middle prev.next = null; // Cut left half: head...prev (null-terminated) TreeNode root = new TreeNode(slow.val); // Middle is root root.left = sortedListToBST(head); // Left: head to prev root.right = sortedListToBST(slow.next); // Right: slow.next to end return root; } ```
The key: we use `prev.next = null` to cut the list at the midpoint.
Trace `1→2→3→4→5`: - slow=3, prev=2. prev.next=null → left=1→2, right=4→5 - root=3 - sortedListToBST(1→2): slow=2,prev=1. root=2. Left=1→null. Right=null. - sortedListToBST(1): single node → root=1. - sortedListToBST(4→5): slow=5,prev=4. root=5. Left=4→null. - sortedListToBST(4): single → root=4. - Tree: [3,2,5,1,null,4] (height-balanced) ✓
**O(n log n) complexity:** Finding the middle takes O(n/2) per level, and there are O(log n) levels → O(n log n). Compare tr-34's O(n) (random access avoids the linear scan).
The Convert to Array First
Collect all values in an array, then apply tr-34's algorithm. O(n) but O(n) extra space.
public TreeNode sortedListToBSTArray(ListNode head) {
List<Integer> vals = new ArrayList<>();
while (head != null) { vals.add(head.val); head=head.next; }
return buildFromArray(vals, 0, vals.size()-1);
}
TreeNode buildFromArray(List<Integer> vals, int lo, int hi) {
if (lo > hi) return null;
int mid = lo+(hi-lo)/2;
TreeNode root = new TreeNode(vals.get(mid));
root.left = buildFromArray(vals, lo, mid-1);
root.right = buildFromArray(vals, mid+1, hi);
return root;
}The Slow-Fast Mid-Cut Recursion
public TreeNode sortedListToBST(ListNode head) {
if (head == null) return null;
if (head.next == null) return new TreeNode(head.val);
ListNode prev = null, slow = head, fast = head;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
prev.next = null; // Cut the list
TreeNode root = new TreeNode(slow.val);
root.left = sortedListToBST(head);
root.right = sortedListToBST(slow.next);
return root;
}Step-by-Step Walkthrough
1→2: fast=2.next=null → loop ends. prev=1,slow=2. prev.next=null. root=2. left=sortedListToBST(1)=1. right=sortedListToBST(null)=null. Tree=[2,1,null] ✅
Deep Insight
**Why is this O(n log n) not O(n)?** Finding the middle of a list of length n takes O(n/2) = O(n). We do this at each level of recursion. Level 0: O(n). Level 1: two calls O(n/2) each = O(n). Total levels = log n → O(n log n).
**O(n log n) vs tr-34's O(n):** The array version has O(1) mid access → O(n) total. The list version has O(n) mid finding → O(n log n) total.
**In-order simulation for O(n):** A smarter approach: do inorder simulation where the BST is built left-to-right matching the sorted list values. O(n) time, O(log n) space.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(n) | Convert to array first |
| Optimal | O(n log n) | O(log n) | Finding mid O(n) per level × O(log n) levels |
Pattern Recognition
✅ Sorted list to BST: slow/fast to find middle ✅ Cut list at prev.next=null ✅ O(n log n) — can't do O(n) without array conversion ✅ In-order simulation achieves O(n) **LeetCode Trigger Phrases:** → "convert sorted list to BST" → Linked list middle + BST construction → Slow/fast pointer + BST recursion
Bhagavad Gita 2.28
अव्यक्तादीनि भूतानि व्यक्तमध्यानि भारत। अव्यक्तनिधनान्येव तत्र का परिदेवना॥
All beings are unmanifest before birth, manifest in the middle state, and unmanifest again at death. What is there to grieve about, O Bharata?
Connection: The sorted linked list is a linear, sequential manifestation of order — each element connected to the next in a chain. The BST reconstruction takes this manifest sequence and builds a balanced, hierarchical structure from it. The middle element of the list — found through patient slow/fast pointer traversal — becomes the root, the point around which all else is organized. From linear sequence to balanced tree: from one form to another, the values remain unchanged.