给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定的有序链表： [-10, -3, 0, 5, 9],
一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
答案：
1public TreeNode sortedListToBST1(ListNode head) {
2 if (head == null) return null;
3 return toBST(head, null);
4}
5
6public TreeNode toBST(ListNode head, ListNode tail) {
7 ListNode slow = head;
8 ListNode fast = head;
9 if (head == tail) return null;
10
11 while (fast != tail && fast.next != tail) {
12 fast = fast.next.next;
13 slow = slow.next;
14 }
15 TreeNode thead = new TreeNode(slow.val);
16 thead.left = toBST(head, slow);
17 thead.right = toBST(slow.next, tail);
18 return thead;
19}
解析：
这题比较简单，因为我们已知链表是有序的，要想转化为高度平衡的二叉树，我们只需要用排序链表的中间节点当做二叉树的根节点，前面部分作为二叉树的左子树，后面部分作为二叉树的右子树，然后在以同样的方式分别递归左右子树即可。再来换种写法
1public TreeNode sortedListToBST(ListNode head) {
2 if (head == null)
3 return null;
4 if (head.next == null)
5 return new TreeNode(head.val);
6 ListNode slow = head, pre = null, fast = head;
7 while (fast != null && fast.next != null) {
8 pre = slow;
9 slow = slow.next;
10 fast = fast.next.next;
11 }
12 pre.next = null;
13 TreeNode n = new TreeNode(slow.val);
14 n.left = sortedListToBST(head);
15 n.right = sortedListToBST(slow.next);
16 return n;
17}
其实思路还都是一样的，其中第12行是相当于把链表两边的前后两部分断开。slow成为当前节点，slow的前部分变成当前节点的左子树，slow的后半部分变成当前节点的右子树。