109.Convert Sorted List to Binary Search Tree

這題就跟convert array的概念是一樣, 從中間開始切分, 這邊linked list找中間node的方法要用快慢指針

另外幾個細節要注意, 你要順便在記錄一個指針, 隨時指向中間的值的前一位, 因為我們要分裂他

另外當head就是那個中間值的時候, 請不要再把head往左子樹去建立, 他會重新在create一個新的node, 就會重複

真的很細節

class Solution {
  public:
     TreeNode *sortedListToBST(ListNode* head) {
        if (!head) return NULL;
        if (!head->next) return new TreeNode(head->val);
        ListNode *slow = head, *fast = head, *last = slow;
        while (fast->next && fast->next->next) {
            last = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = slow->next;
        last->next = NULL;
        TreeNode *cur = new TreeNode(slow->val);
        if (head != slow) cur->left = sortedListToBST(head);
        cur->right = sortedListToBST(fast);
        return cur;
    }
};