Convert Sorted List to Balanced BST

Source

LintCode 106

Problem

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

Solution

public TreeNode sortedListToBST(ListNode head) {  
    int n = 0;
    ListNode cur = head;
    while (cur != null) {
        n++;
        cur = cur.next;
    }
   return helper(new ListNode[] {head}, 0, n-1);
}

public TreeNode helper(ListNode[] A, int start, int end) {
    if (start > end) {
        return null;
    }

    int mid = start + (end - start) / 2;

    TreeNode left = helper(A, start, mid-1);
    TreeNode cur = new TreeNode(A[0].val);
    A[0] = A[0].next;

    cur.left = left;
    cur.right = helper(A, mid+1, end);
    return cur;
}