109.有序链表转换二叉搜索树

题目

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

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

示例:

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

     0
    / \
  -3   9
  /   /
-10  5

方法

本题和108.将有序数组转换为二叉搜索树思路完全一样。
因为链表是升序排列的，所以只要找到它的中间节点，让它成为树的根节点，再让其前面的元素成为左子树，让其后面的元素成为右子树，再对左右子树分别递归进行相同的操作即可。我们用快慢指针法来寻找中间节点。

代码

public TreeNode sortedListToBST(ListNode head) {
    //递归结束条件 + 边界处理
    if(head == null)
        return null;
    if(head.next == null)
        return new TreeNode(head.val);
    //快慢指针法找到中间节点,pre指针用于记录slow的前一个节点
    ListNode slow = head, fast = head, pre = null;
    while(fast != null && fast.next != null){
        pre = slow;
        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;
}