// 109. Convert Sorted List to Binary Search Tree
#include "leetcode.h"

/*
 * given 'head' of a singly linked list where elements are sorted in ascending
 * order convert it to a height balanced binary search tree. meaning the depth
 * of two sub- trees of every node never differs by more than one.
 */

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