给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:给定的有序链表： [-10, -3, 0, 5, 9],
一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
0
/
-3 9
/ /
-10 5
平衡二叉查找树：简称平衡二叉树。由前苏联的数学家Adelse-Velskil和Landis在1962年提出的高度平衡的二叉树，根据科学家的英文名也称为AVL树。它具有如下几个性质：
- 可以是空树。
- 假如不是空树，任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过1
平衡之意，如天平，即两边的分量大约相同。如定义，假如一棵树的左右子树的高度之差超过1，如左子树的树高为2，右子树的树高为0，子树树高差的绝对值为2就打破了这个平衡。如依次插入1，2，3三个结点（如下图）后，根结点的右子树树高减去左子树树高为2，树就失去了平衡。
解题思路：
因为题目要求生成后的二叉搜索树是要平衡的，所以我们在链表中，就以链表的中间节点作为根节点，两边的元素作为根节点的左右子树
以上面的链表为例，我们选取0作为树的根节点，然后我们继续递归，找到中间节点两边的各自的中间节点，把这两个节点作为0的左右子树。
（1）我们可以定义两个指针，分别为fast和low，代表快慢指针，一个走两步，一个走一步，这样我们下来，low节点指向的就是中间节点0。
（2）以-10 到-3，还是通过快慢指针，找到中间节点，5到9，通过快慢指针找到中间节点，如果还有元素，继续找中间节点。。。。
这里我们之所以不采用数组的方式，是因为我们用数组的话，会产生额外的空间复杂度O(N)，尽管解题思路还是很上面的一样，但是我们还是不这么做。
代码如下：
public class LeetCode109 {
public static class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public TreeNode sortedListToBST(ListNode head) {
if (head == null) {
return null;
}
if (head.next == null) {
return new TreeNode(head.val);
}
TreeNode root = getRoot(head);
return root;
}
private TreeNode getRoot(ListNode head) {
if (head == null) {
return null;
}
if (head.next == null) {
return new TreeNode(head.val);
}
ListNode fast = head;
ListNode low = head;
ListNode prev = head;
boolean flag = false;
while (fast != null) {
if (fast.next == null || fast.next.next == null) {
break;
}
prev = low;
fast = fast.next.next;
low = low.next;
flag = true;
}
ListNode next = low.next;
prev.next = null;
TreeNode root = new TreeNode(low.val);
if (prev != head || flag) {
root.left = getRoot(head);
}
root.right = getRoot(next);
return root;
}
}