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

題意：把一個(gè)有序的升序鏈表轉(zhuǎn)化為高度平衡的二叉搜索樹(shù)。

思路：
這道題把108的條件從數(shù)組改為了鏈表，鏈表相比于數(shù)組，求中點(diǎn)沒(méi)有那么方便，因此我們可以把它轉(zhuǎn)為化求數(shù)組。初始化一個(gè)List變量，然后遍歷鏈表，既能求出鏈表長(zhǎng)度，同時(shí)也能把鏈表的每個(gè)節(jié)點(diǎn)值映射到List上，然后應(yīng)用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;
}

自己的這種解法空間復(fù)雜度是O(n)，想看看有沒(méi)有O(1)的方法，想到每次通過(guò)快慢指針求終點(diǎn)的話，時(shí)間復(fù)雜度又很高，沒(méi)想到合適的方法。
看了discuss，發(fā)現(xiàn)了一個(gè)很巧妙的方法，利用中序遍歷的特點(diǎn)，輔以一個(gè)游標(biāo)node初始化指向head，然后隨著中序遍歷每次右移一次，正好可以構(gòu)建出高度平衡的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;
}