1. Problem

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

2. Anylysis

升序的单链表转换成平衡二叉树，那么链表的中点即为二叉树的根节点，然后依次查找出左右的中点，将其作为二叉树的左右子节点。

3. Answer

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; next = null; }
 * }
 */
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedListToBST(ListNode head) throws NullPointerException{
        int len = 0;
        ListNode mHead = head;
        while(mHead != null){
            len ++;
            mHead = mHead.next;
        }
        return sortedListToBST(head, 0, len-1);
    }

    private TreeNode sortedListToBST(ListNode head, int start, int end) {
        if( start > end )
            return null;
        int mid = start + (end-start)/2;
        ListNode mHead = head;
        int mMid = mid;
        while(mMid-- > 0 && mHead != null){
            mHead = mHead.next;
        }
        TreeNode root = new TreeNode(mHead.val);
        root.left = sortedListToBST(head, start, mid-1);
        root.right = sortedListToBST(head, mid+1, end);
        return root;

    }
}

4. Result

Time Limit Exceeded，测试用例的输入数据从-999到4093，大约5000个数据。

时间太长了，分析一下。
每次查找中间节点，为O(N/2)
每次左右子树，需要O(lgN）
因此结果应该是O(NlgN)，不知道分析对不对。
栈调用次数太多了，如何优化呢？
网上有篇文章Convert Sorted List to Balanced Binary Search Tree (BST)。该方法无需寻找链表的中点，采用从底向上遍历建树。

BinaryTree* sortedListToBST(ListNode *& list, int start, int end) {
  if (start > end) return NULL;
  // same as (start+end)/2, avoids overflow
  int mid = start + (end - start) / 2;
  BinaryTree *leftChild = sortedListToBST(list, start, mid-1);
  BinaryTree *parent = new BinaryTree(list->data);
  parent->left = leftChild;
  list = list->next;
  parent->right = sortedListToBST(list, mid+1, end);
  return parent;
}

BinaryTree* sortedListToBST(ListNode *head, int n) {
  return sortedListToBST(head, 0, n-1);
}