109. Convert Sorted List to Binary Search Tree

, 
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
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return new TreeNode(head.val);
        }

        // 1 -> 2
        // f         f
        // s    s

        // 1 -> 2 -> 3
        // f         f
        // s    s

        ListNode fast = head, slow = head, midPre = null;

        // split to: [head, midPre] | [slow, tail]
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            midPre = slow;
            slow = slow.next;
        }

        TreeNode root = new TreeNode(slow.val);
        midPre.next = null;
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(slow.next);
        return root;
    }
}

References

109. Convert Sorted List to Binary Search Tree