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

 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 }