109 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.
Solution
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* sortedListToBST(ListNode* head) {
if ( head == NULL ) return NULL;
int length = 0;
ListNode *p = head;
while ( p != NULL ) {
p = p->next;
length += 1;
}
TreeNode *tnode;
if ( length == 1 ) {
tnode = new TreeNode(head->val);
return tnode;
}
int n = length/2 + 1; // n-th node is the root
// find (n-1)th node
p = head;
for ( int i = 1; i <= n-2; i++ ) p = p->next;
ListNode *proot = p->next;
p->next = NULL;
tnode = new TreeNode(proot->val);
tnode->left = sortedListToBST(head);
tnode->right = sortedListToBST(proot->next);
return tnode;
}
};