Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

这题我一看到，觉得跟上题(108)一样啊，就是找中间结点递归生成BST。于是我先用了个笨方法先用O(n)时间把list上的元素撸下来保存到nums里，跑了一下，AC了。这方法可行，但占用了O(n)空间存储。

不好的方法

//不好的方法
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        List<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        int[] nums = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            nums[i] = list.get(i);
        }

        return recursion(nums, 0, nums.length - 1);
    }

    private TreeNode recursion(int nums[], int left, int right) {
        if (left > right) return null;
        int mid = (left + right) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = recursion(nums, left, mid - 1);
        root.right = recursion(nums, mid + 1, right);

        return root;
    }

好的方法：

还是看到SOLUTIONS里的高票答案，直接构造BST，中点用快慢指针寻找。
注意：

1.     if (head == tail) return null;这个判断条件不能少。
   

2.     while里的判断条件可以看成一个routine了，而且是!=tail，不是null
   

    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        return recursion(head, null);

    }
  
    private TreeNode recursion(ListNode head, ListNode tail) {
        ListNode runner = head;
        ListNode walker = head;
        //这个return不能少
        if (head == tail) return null;
        //这while里的判断条件可以看成一个routine了，而且是!=tail，不是null
        while (runner.next != tail && runner.next.next != tail) {
            walker = walker.next;
            runner = runner.next.next;
        }
        TreeNode root = new TreeNode(walker.val);
        root.left = recursion(head, walker);
        root.right = recursion(walker.next, tail);

        return root;
    }