给定一个单链表的头节点 head ，其中的元素 按升序排序 ，将其转换为 平衡 二叉搜索树。
示例 1:
输入: head = [-10,-3,0,5,9] 输出: [0,-3,9,-10,null,5] 解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树。
示例 2:
输入: head = [] 输出: []
提示:
head中的节点数在[0, 2 * 104]范围内-105 <= Node.val <= 10
思路：先获取到链表的长度，然后去递归构造树即可，每次构造的树节点永远是链表或子链表的中心，但是由于是单向链表，所以每次获取链表中的节点的时候就会导致每次都从头开始，可以用循环链表改善，如果要构造的节点的坐标大于length/2的时候就next length -index次，然后递归构造，设置临界条件即可，若length为0就是无节点，如果length为1就是叶子节点。然后上代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
ListNode temp;
public TreeNode sortedListToBST(ListNode head) {
temp = head;
// 思路就是取链表的中心节点，作为总树或子树的根节点，然后循环、递归
int length = getListLength(head);
return buildTree(0, length);
}
public TreeNode buildTree(int start ,int length) {
int i = 0;
ListNode t = temp;
while (i < start + length/2) {
t = t.next;
i++;
}
// 如果是0，直接为null
if (length == 0) return null;
// 如果length为1的时候，直接返回，因为它已经是树叶节点了
if (length == 1) return new TreeNode(t.val, null, null);
// 遍历到中心节点，就构造节点
return new TreeNode(t.val, buildTree(start, length/2), buildTree(start + length/2 +1, length-1-length/2));
}
// 获取节点总节点数
public int getListLength(ListNode head) {
int length = 0;
while(head != null) {
length++;
head = head.next;
}
return length;
}
}快慢指针也是解决中间值问题的一个快速的解决办法，思路相同，只是取中间值的方法不同。
class Solution {
public TreeNode sortedListToBST(ListNode head) {
return buildTree(head, null);
}
public TreeNode buildTree(ListNode left, ListNode right) {
if (left == right) {
return null;
}
ListNode mid = getMedian(left, right);
TreeNode root = new TreeNode(mid.val);
root.left = buildTree(left, mid);
root.right = buildTree(mid.next, right);
return root;
}
public ListNode getMedian(ListNode left, ListNode right) {
ListNode fast = left;
ListNode slow = left;
while (fast != right && fast.next != right) {
fast = fast.next;
fast = fast.next;
slow = slow.next;
}
return slow;
}
}