Convert Sorted List into a BST

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

               2
1->2->3  =>   / \
             1   3

思路1：自顶而下

1. 与Convert Sorted Array into BST思想类似，用快慢指针，每次找到链表的中点节点，这个就是根节点。
2. 链表的左半部分就是左子树，而右半部分则是右子树。
3. 继续递归处理相应的左右部分，就能够构造出对应的二叉树了。

时间复杂度O(nlgN)

思路2：自底而上

sorted链表的顺序就是inorder的顺序，所以我们可以根据inorder的算法来实现顺序遍历链表，然后建树的过程。

• 对于有序链表，BST的根节点是其中点；
• 该根节点的左子树的根节点，是左半边的中点；
• 该根节点的右子树的根节点，又是右半边的中点；
  以此往复，链表第一个节点，就是最左边左子树的根节点，而最左边左子树的左节点和右节点都是空。

1. 由于需要不断更新当前链表的curNode，就需要在class下维护一个global的curNode。
2. 用start和end两个值来限定子树在链表中的位置(初始start = 0, end = 链表length - 1）。当 Start > End, 说明找到了叶子节点的左右子节点，返回null。
3. ->递归构建左子树
   ->然后用链表的头指针创建curRootNode
   -> 更新链表头指针
   -> 递归构建右子树
   ->链接CurRootNode和其左右子树
   ->返回CurRootNode

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private ListNode curNode;
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        curNode = head;
        int len = 0;
        
        while (head != null) {
            len++;
            head = head.next;
        }
        
        return convertBST(0, len - 1);
    }
    
    //用inorder来建立树
    private TreeNode convertBST(int start, int end) {
        //找到的叶子节点下的空节点了，递归停止
        if (start > end) {
            return null;
        }
        int mid = start + (end - start) / 2;
        
        //1. find the leftNode
        TreeNode left = convertBST(start, mid - 1);
        //2. create the current root Node
        TreeNode curRoot = new TreeNode(curNode.val);
        //3. update the current node of LinkedList
        curNode = curNode.next;
        //4. find the right Node
        TreeNode right = convertBST(mid + 1, end);
        //5.connect 
        curRoot.left = left;
        curRoot.right = right;
        
        return curRoot;
    }
}