109. 有序链表转换二叉搜索树
给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定的有序链表： [-10, -3, 0, 5, 9],
一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
0
/
-3 9
/ /
-10 5
思路
二叉搜索（查找）树定义：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的结点。
1 使用快慢指针法，找到链表的中间节点，该节点即为二叉查找树的根节点
2 将根节点与前面链表断开，再递归前后两个链表，递归方法最终返回根节点
代码
class Solution {
public TreeNode sortedListToBST(ListNode head) {
if (head == null) {
return null;
}
if (head.next == null){
return new TreeNode(head.val);
}
//pre节点指向slow的前节点
ListNode pre = new ListNode(0, head);
ListNode slow = head;
ListNode fast = head;
//fast走两步，slow走一步，当fast走完，slow则是中间节点，即为root
while (fast != null && fast.next != null){
pre = pre.next;
slow = slow.next;
fast = fast.next.next;
}
pre.next = null;
TreeNode root = new TreeNode(slow.val);
root.left = sortedListToBST(head);
root.right = sortedListToBST(slow.next);
return root;
}
}