转换AVL树

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

示例:

给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

解题思路：
1.题中我们得知，这是一个升序链表，所以我们不需要根据节点的value再来判断添加到左还是右节点
2.由于二叉搜索树要求左右子树高度差<=1，所以我们取链表的中点作为根节点，如果链表个数为偶数，那么左边比右边少一个，如果链表个数为奇数，那么左右个数恰好相等
3.那么整棵树的root找到了，左子树的root其实就是左子树的中点，右子树同理，我们利用分治的思想，可以一直递归下去，直到左==右，则return null，我们返回已经排好的子节点
4.关于找链表中点我们可以用快慢指针的方法

public TreeNode sortedListToBST(ListNode head) {
        return dfsFillNode(head, null);
    }
	public TreeNode dfsFillNode(ListNode left,ListNode right) {
		if(left == right)
			return null;
		ListNode mid = findMiddleNode(left,right);
		TreeNode root = new TreeNode(mid.val);
		root.left = dfsFillNode(left, mid);
		root.right = dfsFillNode(mid.next, right);
		return root;
	}
	public ListNode findMiddleNode(ListNode node,ListNode right) {
		ListNode fast = node;
		ListNode slow = node;
		while(fast!=right&&fast.next!=right) {
			fast = fast.next.next;
			slow = slow.next;
		}
		return slow;
	}