[LeetCode] 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.
Analysis:
If we create a balanced BST using a sorted array, it will be much easier, because we access each element of the array very easily. And the tree can be created by pre-order.
Note, with linked list, we can only easily access the element from left to right, which indicates that we might be able to create the tree by in-order. Each time we create a tree node, we move the linked list pointer to the next.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *listToTreeInner(ListNode*& head, int start, int end) 
    {
        if(start > end) return NULL;
        int mid = start + (end-start)/2;
        TreeNode *leftNode = listToTreeInner(head, start, mid-1);
        TreeNode *current = new TreeNode(head->val);
        current->left = leftNode;
        //Note, we move head to the next for the next node
        head = head->next;
        TreeNode *rightNode = listToTreeInner(head, mid+1, end);
        current->right = rightNode;
        return current;
    }

    TreeNode *sortedListToBST(ListNode *head) 
    {
        if(!head) return NULL;
        int last = 0;
        ListNode* p = head;
        while(p->next) {
            last++;
            p = p->next;
        }
        return listToTreeInner(head, 0, last);
    }
};