本文共 995 字，大约阅读时间需要 3 分钟。

109. 有序链表转换二叉搜索树

难度中等

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

思路1.0：

将有序链表视为一个无限向右子树衍生的二叉树，那么这题就变为了：二叉树转变为平衡二叉树的问题。

思路2.0（已看题解）：

快慢指针

代码1.0：

class Solution {
      public:       TreeNode* sortedListToBST(ListNode* head) {
              if (head == NULL) return NULL;           if (head->next == NULL) return new TreeNode(head->val);;           //先找到根节点           ListNode* fastP = head;           ListNode* slowP = head;           ListNode* preSlowP = NULL;           while (fastP != NULL && fastP->next != NULL) {
                  preSlowP = slowP;               slowP = slowP->next;               fastP = fastP->next->next;           }           preSlowP->next = NULL;           TreeNode* root = new TreeNode(slowP->val);           root->left = sortedListToBST(head);           root->right = sortedListToBST(slowP->next);           return root;       }   };

查找链表中间节点，就用“快慢指针”！

转载地址：http://zvowi.baihongyu.com/