Leetcode 109. Convert Sorted List to Binary Search Tree

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

题意：把一个有序的升序链表转化为高度平衡的二叉搜索树。

思路：
这道题把108的条件从数组改为了链表，链表相比于数组，求中点没有那么方便，因此我们可以把它转为化求数组。初始化一个List变量，然后遍历链表，既能求出链表长度，同时也能把链表的每个节点值映射到List上，然后应用108的解法就可以了。

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

    List<Integer> list = new ArrayList<>();
    int length = 0;
    ListNode dummy = head;
    while (dummy != null) {
        list.add(dummy.val);
        length++;
        dummy = dummy.next;
    }

    return helper(1, length, list);
}

public TreeNode helper(int start, int end, List<Integer> list) {
    if (start > end) {
        return null;
    }

    int middle = start + (end - start) / 2;
    TreeNode root = new TreeNode(list.get(middle));
    root.left = helper(start, middle - 1, list);
    root.right = helper(middle + 1, end, list);

    return root;
}

自己的这种解法空间复杂度是O(n)，想看看有没有O(1)的方法，想到每次通过快慢指针求终点的话，时间复杂度又很高，没想到合适的方法。
看了discuss，发现了一个很巧妙的方法，利用中序遍历的特点，辅以一个游标node初始化指向head，然后随着中序遍历每次右移一次，正好可以构建出高度平衡的BST，十分精彩。

private ListNode node;

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

    int size = 0;
    ListNode runner = head;
    node = head;

    while(runner != null){
        runner = runner.next;
        size ++;
    }

    return inorderHelper(0, size - 1);
}

public TreeNode inorderHelper(int start, int end){
    if(start > end){
        return null;
    }

    int mid = start + (end - start) / 2;
    TreeNode left = inorderHelper(start, mid - 1);

    TreeNode treenode = new TreeNode(node.val);
    treenode.left = left;
    node = node.next;

    TreeNode right = inorderHelper(mid + 1, end);
    treenode.right = right;

    return treenode;
}