Day 42, #92, #109, Reverse Linked List II, Convert Sorted List to Binary Search Tree

Reverse Linked List II
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given m, n satisfy the following condition:
1 ? m ? n ? length of list.
----------------------------------------
lets say m = 3, n = 5
1             2              3             4             5            6
|              |                |                             |
head      left           tail                     newHead

/* Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        ListNode *newHead = NULL, *itr = head,*left = NULL,*tail;
        // move to m-th node
        for (int i = 1; i < m; i++) {
            left = itr;
            itr = itr->next;
        }
        tail = itr;
        // move to n-th node
        for (int i = m; i <= n; i++) {
            ListNode *temp = itr->next;
            itr->next = newHead;
            newHead = itr;
            itr = temp;
        }
        tail->next = itr;
        if (m == 1) {
            return newHead;
        }
        left->next = newHead;
        return head;
    }
};

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.
--------------------------------------------------------------------------
Further reading:
http://leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html
http://www.geeksforgeeks.org/sorted-linked-list-to-balanced-bst/

/**
 * 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* constructTree (ListNode *&list,int start, int end) {
        if (start > end) {
            return NULL;
        }
        int mid = start + (end - start) / 2;
        TreeNode *left = constructTree(list,start,mid - 1);
        TreeNode *root = new TreeNode(list->val);
        root->left = left;
        list = list->next;
        root->right = constructTree(list,mid + 1, end);
        return root;
    }


    TreeNode *sortedListToBST(ListNode *head) {
        int n = 0;
        ListNode *itr = head;
        while (itr != NULL ) {
            n++;
            itr = itr->next;
        }
        return constructTree(head,0,n-1);
    }
};

Update Nov-21-2014
Bottom up solution. For each node, build the left child -> root -> right child, follow the in order sequence