[109] Convert Sorted List to Binary Search Tree

咦竟然過了

也太感人了吧!!!

雖然不是很美，但是先降子吧XD（也太得過且過了XD）

如果是現在回去考某公司的筆試，應該會過吧QQ 嗚嗚嗚嗚嗚嗚嗚

/**

* 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* sortedListToBST(struct ListNode* head){

if (head == NULL)

return NULL;

struct ListNode *pre= NULL;

struct ListNode *slow, *fast;

slow=head;

fast=head;

while (fast->next !=NULL)

{

pre = slow;

slow=slow->next;

fast= fast->next;

if (fast->next != NULL)

fast = fast->next;

}

//printf("%d %d %d\n", pre->val, slow->val, fast->val);

struct TreeNode *ret = calloc(1,sizeof(struct TreeNode));

ret->val = slow->val;

if (pre==NULL)

ret->left = NULL;

else

{

pre->next = NULL;

ret->left = sortedListToBST(head);

}

if (slow->next == NULL)

ret->right = NULL;

else

ret->right = sortedListToBST(slow->next);

return ret;

}