convert sorted list to binary search tree

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

This is my simple code: simple recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
TreeNode* sortedListToBST(ListNode* head) {
if(!head) return NULL;
if(!(head->next)) return new TreeNode(head->val);
ListNode *fast = head, *slow = head, *pre = NULL;
while(fast && fast->next){
pre = slow;
fast = fast->next->next;
slow = slow->next;
}
TreeNode *root = new TreeNode(slow->val);
pre->next = NULL;
root->left = sortedListToBST(head);
root->right = sortedListToBST(slow->next);
return root;
}
};

This is a strange way:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
TreeNode* sortedListToBST(ListNode* head) {
int size=0;
ListNode *save=head;
while(head){
size++;
head = head->next;
}
head = save;
TreeNode* root = helper(head,size);
return root;
}
TreeNode* helper(ListNode*& head,int size){
if(head==NULL ||size<=0) return NULL;
int rightSize = (size-1)/2;
TreeNode* left = helper(head,size-1-rightSize);
TreeNode* root = new TreeNode(head->val);
head = head->next;
root->left = left;
root->right = helper(head,rightSize);
return root;
}
};

Contents
,