109. Convert Sorted List to Binary Search Tree

The intuitive idea is to recursively construct binary search tree. There are two ways. First solution is using a counter.

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

The second solution uses slow and fast pointer to find the middle node. This is a little bit faster than the first one because it saves one entire list scan.

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