# Question

Formatted question description: https://leetcode.ca/all/109.html

109	Convert Sorted List to Binary Search Tree

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



# Algorithm

The idea is exactly the same as the previous Convert Sorted Array to Binary Search Tree, except that the data types of operations are different, one is an array and the other is a linked list. Arrays are convenient because you can directly access any element through index, but linked lists cannot. Because the binary search method needs to find the midpoint every time.

After finding the midpoint, we need to establish a root node of the number based on the midpoint value, and then we need to disconnect the original linked list and divide it into two linked lists, neither of which can contain the original midpoint, and then recursively call the two linked lists separately Original function, connected to the left and right child nodes respectively.

# Code

Java

public class Convert_Sorted_List_to_Binary_Search_Tree {

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; next = null; }
* }
*/
/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {

return null;
}
}

// find mid
ListNode dummy = new ListNode(0);
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}

// prev is one before mid
prev.next = null; // @note: cut

TreeNode root = new TreeNode(slow.val);