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

分析

将链表转化为平衡的二叉排序树，可以用上一题的思路，将中间的点作为根节点，左边的为左子树，右边的为右子树。依次递归即可。由于链表统计长度比较麻烦，先转化为数组即可。
也可以使用一个指针走一步，另一个指针走两步来获得中间的结点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* convert(int* nums,int numsSize,int left,int right)
{
    if(left<=right)
    {
        struct TreeNode *rootNode=(struct TreeNode *)malloc(sizeof(struct TreeNode ));
        rootNode->val=nums[(left+right)/2];
        rootNode->left=convert(nums,numsSize,left,(left+right)/2-1);
        rootNode->right=convert(nums,numsSize,(left+right)/2+1,right);
        return rootNode;
    }
    return NULL;
}
int nums[100000];
struct TreeNode* sortedListToBST(struct ListNode* head) {
    int numsSize=0;
    struct ListNode *temp=head;
    while(temp!=NULL)
    {
        nums[numsSize]=temp->val;
        temp=temp->next;
        numsSize++;
    }
    if(numsSize==0)return NULL;
    else
        return convert(nums,numsSize,0,numsSize-1);
}