106. Convert Sorted List to Binary Search Tree

class Solution { public: /* * @param head: The first node of linked list. * @return: a tree node */ TreeNode * sortedListToBST(ListNode * head) { // write your code here // Divide and conquer //1, slow and fast pointers finding the mid //2, pick the middle as root node //3, Divide //4, conquer if(head == NULL){ return NULL; } if(head->next == NULL){ TreeNode *root = new TreeNode(head->val); return root; } ListNode *dummy = new ListNode(0); dummy->next = head; ListNode *copy = head; ListNode *slow = head; ListNode *fast = head->next; ListNode *pre = dummy; while(fast != NULL && fast->next != NULL){ pre = slow; slow = slow->next; fast = fast->next->next; } pre->next = NULL; TreeNode *root = new TreeNode(slow->val); root->left = sortedListToBST(dummy->next); root->right = sortedListToBST(slow->next); return root; } };