# 109. Convert Sorted List to Binary Search Tree (Java Solution)

• ``````/**
* 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) {
if (head == null) {
return null;
}

int len = len(head);

if (len == 1) {
return new TreeNode(head.val);
}

ListNode justBeforeMiddle = head;

for (int i=0; i < len/2 -1; i++) justBeforeMiddle = justBeforeMiddle.next;

ListNode middle = justBeforeMiddle.next;
justBeforeMiddle.next = null;

TreeNode root = new TreeNode(middle.val);

root.left = sortedListToBST(head);
root.right = sortedListToBST(middle.next);

return root;
}

public int len(ListNode head) {
if (head == null) {
return null;
}
return 1 + len(head.next);
}
}

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.