题解 | #有序链表变成二叉搜索树#

其实（fast!=null&&fast.next!=null）之前一直写成了(fast.next!=null&&fast.next.next!=null)，结果就不对了。

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @return TreeNode类
     */
    public TreeNode sortedListToBST (ListNode head) {
        // write code here
        if(head==null)
            return null;

        if(head.next==null)
            return new TreeNode(head.val);

        ListNode slow = head;
        ListNode fast = head;
        ListNode preMid = null;

        while(fast!=null&&fast.next!=null){
            preMid = slow;
            slow = slow.next;
            fast = fast.next.next;
        }

        TreeNode root = new TreeNode(slow.val);
        preMid.next = null;
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(slow.next);

        return root;
    }
}