# Convert Sorted List to Binary Search Tree

This is No.109 in leetcode.

Below is the 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 {

// The pointer used to disconnect the left half from the mid node.
ListNode prevPtr = null;

// Iterate until fastPr doesn't reach the end of the linked list.
while (fastPtr != null && fastPtr.next != null) {
prevPtr = slowPtr;
slowPtr = slowPtr.next;
fastPtr = fastPtr.next.next;
}

// Handling the case when slowPtr was equal to head.
if (prevPtr != null) {
prevPtr.next = null;
}

return slowPtr;
}

// If the head doesn't exist, then the linked list is empty
return null;
}

// Find the middle element for the list.

// The mid becomes the root of the BST.
TreeNode node = new TreeNode(mid.val);

// Base case when there is just one element in the linked list
return node;
}

// Recursively form balanced BSTs using the left and right halves of the original list.