# 109 Convert Sorted List to Binary Search Tree – Medium

### Problem:

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

### Thoughts:

This is similar to the Sorted Array version of the problem.

It’s easier for sorted array because we could always easily find the mid element.

But for a sorted list, we cannot visit element randomly, can only visit in order.

So here in order to make code clean and easy, we are pretending we could get the mid element.

### Solutions:

``````/**
* 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; }
* }
*/
public class Solution {
ListNode p = new ListNode(-1);
int count = 0;
while (node!=null) {
count ++;
node = node.next;
}
return gt(p, 0, count - 1);
}
private TreeNode gt(ListNode p, int start, int end){
if (start > end) {
return null;
}
int mid = (start + end) / 2;
TreeNode left = gt(p, start, mid - 1);
TreeNode root = new TreeNode(p.next.val);
p.next = p.next.next;
TreeNode right = gt(p, mid + 1, end);
root.left = left;
root.right = right;
return root;
}
}
``````