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:** []
Example 3:
**Input:** head = [0]
**Output:** [0]
Example 4:
**Input:** head = [1,3]
**Output:** [3,1]
Constraints:
The number of nodes in head is in the range [0, 2 * 104].
-105 <= Node.val <= 105
ac
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedListToBST(ListNode head) {
// corner case, exit
if (head == null) return null; // len == 0
if (head.next == null) return new TreeNode(head.val); // len == 1
// find mid
ListNode slow = head, fast = head;
ListNode prev = new ListNode(0);
prev.next = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
prev = prev.next;
}
// seperate
ListNode h2 = slow.next;
slow.next = null;
prev.next = null;
// divide & conquer
TreeNode root = new TreeNode(slow.val);
root.left = sortedListToBST(head);
root.right = sortedListToBST(h2);
return root;
}
}
