109. Convert Sorted List to Binary Search Tree

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;
    }
}

Reference