Convert Sorted List to Balanced BST

题目：

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

分析：

这是一个典型的divide and conquer的题目，第二遍做到这里的时候，也不算做错，大致思路是有的，只是并不熟练。

解法：

class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: a tree node
     */
    ListNode* findMiddle(ListNode* head) {
        if (head == NULL || head->next == NULL) {
            return head;
        }

        ListNode dummy(0);
        dummy.next = head;

        ListNode* slow = &dummy;
        ListNode* fast = &dummy;

        while (fast->next != NULL && fast->next->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
        } 
        return slow;
    }

    TreeNode *sortedListToBST(ListNode *head) {
        // write your code here
        if (head == NULL) {
            return NULL;
        }

        if (head->next == NULL) {
            TreeNode* root = new TreeNode(head->val);
            return root;
        }

        ListNode* prevMid = findMiddle(head);
        ListNode* mid = prevMid->next;
        prevMid->next = NULL;

        ListNode* newhead = mid->next;
        mid->next = NULL;

        TreeNode* root = new TreeNode(mid->val);
        root->left = sortedListToBST(head);
        root->right = sortedListToBST(newhead);

        return root;
    }
};