[leetcode_109]Convert Sorted List to Binary Search Tree

This problem is a variation of http://blog.sina.com.cn/s/blog_672f71fc0101os5r.html.
The only difference is that the array is replaced with a singly linked list. When searching in the linked list, be careful to optimize: after each binary split, the head node remains the same for the left part, but for the right part, the head node needs to be updated to the mid node. Otherwise it will time out.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    ListNode * GetListNthNode(ListNode * head, int n) {
        int k = 0;
        while(k < n) {
            k++;
            head = head->next;
        }
        return head;
    }
    int CountList(ListNode *head) {
        int count = -1;
        while(head != NULL) {
            head = head->next;
            count++;
        }
        return count;
    }
    TreeNode *BSearchT(int left, int right, ListNode * head) {
        if(right < left) return NULL;
        int mid = (left + right) / 2;
        TreeNode * root = new TreeNode(GetListNthNode(head, mid - left)->val);
        root->left = BSearchT(left, mid - 1, head);
        root->right = BSearchT(mid + 1, right, GetListNthNode(head, mid + 1 - left));
        return root;
    }
    TreeNode *sortedListToBST(ListNode *head) {
        if(head == NULL)
            return NULL;
        int n = CountList(head);
        int mid = (0 + n) / 2;
        TreeNode * root = new TreeNode(GetListNthNode(head, mid)->val);
        root->left = BSearchT(0, mid - 1, head);
        root->right = BSearchT(mid + 1, n, GetListNthNode(head, mid + 1));
        return root;
    }
};