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;
    }
}