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

题目链接：https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/

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

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

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     struct ListNode *next;
 6  * };
 7  */
 8 /**
 9  * Definition for a binary tree node.
10  * struct TreeNode {
11  *     int val;
12  *     struct TreeNode *left;
13  *     struct TreeNode *right;
14  * };
15  */
16 
17 struct TreeNode* sortedListToBST(struct ListNode* head){
18     if(head==NULL) return NULL;
19     struct ListNode *slow=head,*fast=head,*tmp=head;
20     while(fast->next&&fast->next->next){
21         tmp=slow;
22         slow=slow->next;
23         fast=fast->next->next;
24     }
25     struct TreeNode *top=(struct TreeNode*)malloc(sizeof(struct TreeNode));
26     top->val=slow->val;
27     if(tmp==slow){
28         top->left=NULL;
29     }else{
30         tmp->next=NULL;
31         top->left=sortedListToBST(head);
32     }
33     top->right=sortedListToBST(slow->next);
34     return top;
35 }