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.

tags: depth-first-search, linked list

版本一，每次取链表的中点作为root，左右分别递归调用。
我为了方便通过index取ListNode，便把list复制成了ector，却报出内存超出限额错误。尝试改进，不加vector，用时间换空间的方法。

/**
 * 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:
    vector<ListNode*> listnode;
    TreeNode *sortedListToBST(ListNode *head) {
        while(head != NULL){
            listnode.push_back(head);
            head = head->next;
        }
        return _sortedListToBST(listnode, 0, listnode.size());
    }
    TreeNode * _sortedListToBST(vector<ListNode *>nodes, int start, int end){
        if (start >= end){
            return NULL;
        }    
        else if(start + 1 == end){
            TreeNode * p = new TreeNode(nodes[start]->val);
            p->left = p->right = NULL;
            return p;
        }
        else{
           int mid = (end + start) / 2;
           TreeNode * p = new TreeNode(nodes[mid]->val);
           p->left = _sortedListToBST(nodes, start, mid);
           p->right = _sortedListToBST(nodes, mid + 1, end);
           return p;
        }
    }
};

版本二：直接在ListNode上操作，AC。需要注意的是，我们需要在递归函数中，每次都更新head的位置。因为算法中耗时的部分在getNodeById这里，我们应该每次都缩小list的长度，以减少时间开销。

时间复杂度O(nlogn)

/**
 * 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 *sortedListToBST(ListNode *head) {
        int n = getListLength(head);
        return _sortedListToBST(head, n);
    }
    TreeNode * _sortedListToBST(ListNode * head, int count){
        if (count == 0){
            return NULL;
        }    
        else if(count == 1){
            TreeNode * p = new TreeNode(head->val);
            p->left = p->right = NULL;
            return p;
        }
        else{
           int mid = count / 2;
           ListNode * midNode = getNodeByIndex(head, mid);
           TreeNode * p = new TreeNode(midNode->val);
           p->left = _sortedListToBST(head, mid);
           p->right = _sortedListToBST(midNode->next, count - mid - 1);
           return p;
        }
    }
    int getListLength(ListNode * head){
        int i;
        for(i = 0; head != NULL; i++){
            head = head->next;
        }
        return i;
    }
    ListNode * getNodeByIndex(ListNode * head, int idx){
        while(idx--){
            head = head->next;
        }
        return head;
    }
};