[数据结构与算法]有序链表转换成二叉搜索树 C语言

题目描述：

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

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

解题思路：

对于高度平衡二叉树对每个结点都要满足左右子树的高度差绝对值不超过1。我们可以将链表的中间结点作为根节点建立二叉树，左侧和右侧的结点分别作为左孩子和右孩子，然后递归建立整个二叉树。
这样建成的二叉树对于每一个结点，其左右子树的高度差绝对值不超过1。

• 使用快慢指针寻找链表的中间结点
  快指针fast 和 慢指针slow先指向表头left。在循环体中，fast一次走两步，slow一次走一步，相当 于在相同的时间里，fast的速度时slow速度的两倍，则slow走的路程就是fast的一半，所以slow指向链 表的中间结点。

//寻找中间结点   快慢指针法
struct ListNode *findMidNode(struct ListNode *left,struct ListNode *right)
{
    struct ListNode *slow,*fast;
    slow = fast = left;
    while(fast != right && fast->next != right)			//快指针一次走两步  慢指针一次走一步
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;				//最后慢指针会指向链表的中间
}

//建树   递归法
struct TreeNode * buildTree(struct ListNode *left,struct ListNode *right)
{
    if(left == right)
        return NULL;
    struct TreeNode *root = malloc(sizeof(struct TreeNode));			//根节点
    struct ListNode *mid = findMidNode(left,right);					//链表的中间结点
    root->val = mid->val;
    root->left = buildTree(left,mid);				//左孩子
    root->right = buildTree(mid->next,right);				//右孩子
    return root;
}   

struct TreeNode* sortedListToBST(struct ListNode* head){
    return buildTree(head,NULL);
}