【leetcode】Convert Sorted List to Binary Search Tree （middle）
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
思路：题目看上去好像很难，但实际上很简单，递归做就行，每次找到左右子树对应的子链表就行。一次AC。
class Solution { public: TreeNode *sortedListToBST(ListNode *head) { if(head == NULL) return NULL; ListNode * fast = head, *slow = head, *slowpre = head; //分别是快指针、慢指针、慢指针前一个指针 慢指针的位置就是当前平衡树根节点的位置 中间值 while(fast != NULL && fast->next != NULL) { fast = fast->next->next; slowpre = slow; slow = slow->next; } TreeNode * root = new TreeNode(slow->val); ListNode * left = (slow == head) ? NULL : head; //如果慢指针==头指针 则其左子树是空的 ListNode * right = slow->next; slowpre->next = NULL; //左子树对应的链表末尾置null root->left = sortedListToBST(left); root->right = sortedListToBST(right); return root; } };