ConvertSortedListtoBinarySearchTree.java

/**
 * Given a singly linked list where elements are sorted in ascending order, convert it to a height
 * balanced BST.
 */
public class ConvertSortedListtoBinarySearchTree {
 public TreeNode sortedListToBST(ListNode head) {
 return sortedListToBST(head, null);
 }

 private TreeNode sortedListToBST(ListNode start, ListNode end) {
 if (start == end) {
 return null;
 } else if (start.next == end) {
 return new TreeNode(start.val);
 } else {
 ListNode fast = start, slow = start;
 while (fast.next != end && fast.next.next != end) {
 fast = fast.next.next;
 slow = slow.next;
 }
 TreeNode left = sortedListToBST(start, slow);
 TreeNode right = sortedListToBST(slow.next, end);
 TreeNode root = new TreeNode(slow.val);
 root.left = left;
 root.right = right;
 return root;
 }
 }
}