Convert Sorted List to Binary Search Tree - LeetCode 109

题目描述：

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Hide Tags Depth-first Search Linked List

分析：

思路与108题 http://blog.csdn.net/bu_min/article/details/45937747 的将有序数组转换为平衡二叉搜索树。

每次找出中间位置的元素作为根节点，然后递归构造左子树和右子树。

但是本题是一个有序的链表，要找出中间元素和将链表分为左右子树两段比分割数组麻烦。

找中间元素的方法：利用快慢指针，慢指针每次移动一个位置，快指针每次移动两个位置，知道快指针指向NULL或下一个元素是NULL时，慢指针所指的元素就是中间元素。

但是这样的话，无法取出左子树对应的子链表（因为无法删除中间元素，即将慢指针无法回退一个位置）。

解决方法是当慢指针指向中间元素的上一个元素时，停止快慢指针的移动即可。调整指针移动的循环条件，即快指针后面最少有3个非空结点时才移动快慢指针。当不满足此条件是，停止移动，此时中间元素是慢指针的下一个元素，右子树开始的元素是慢指针的下下个元素，这样就能分割出左右两个字数对应的链表了。

由于要保证快指针后面至少有3个非空节点时才移动快慢指针，那么得分别处理链表节点数目少于4的情况。

以下是C++实现代码：

/**///32ms*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
     TreeNode* sortedListToBSTHelp(ListNode* node){
        if (node == NULL) //空链表
            return NULL;
        if(node->next == NULL){ //只有1个结点
            TreeNode* root = new TreeNode(node->val);
            return root;
        }
        if(node->next->next == NULL){ //只有2个结点
            TreeNode* root = new TreeNode(node->val);
            root->right = new TreeNode(node->next->val);
            return root;
        }
        if(node->next->next->next == NULL){ //只有 3个结点
            TreeNode* root = new TreeNode(node->next->val);
            root->left = new TreeNode(node->val);
            root->right = new TreeNode(node->next->next->val);
            return root;
        }

 	//大于3个结点
        ListNode* s = node;
        ListNode* f = node;
        while(f != NULL && f->next !=NULL &&f->next->next!= NULL && f->next->next->next != NULL){
            s = s->next;
            f = f->next->next;
        }
        TreeNode* root = new TreeNode(s->next->val); //根节点为慢指针的下一个元素
        ListNode* rig = s->next->next; //右子树对应的子链表
        s->next = NULL; //分割出左子树对应的子链表
        root->left = sortedListToBSTHelp(node); //构造左子树
        root->right = sortedListToBSTHelp(rig); //构造右子树
        return root;
    }
    TreeNode* sortedListToBST(ListNode* head) {
        if(head == NULL)
            return NULL;
       
        return sortedListToBSTHelp(head);
    }
};