Untitled

class Solution {
    // Definition for singly-linked list.
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) {
            this.val = val;
            this.next = null;
        }
    }

    // Definition for a binary tree node.
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val) {
            this.val = val;
            this.left = null;
            this.right = null;
        }
    }

    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return new TreeNode(head.val);
        }

        // Find the middle node and make it the root
        ListNode slow = head;
        ListNode fast = head;
        ListNode slowPrev = null;

        while (fast != null && fast.next != null) {
            slowPrev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }

        // Disconnect the left half from the middle node
        if (slowPrev != null) {
            slowPrev.next = null;
        }

        TreeNode root = new TreeNode(slow.val); // Make root
        root.left = sortedListToBST(head);      // Build left subtree
        root.right = sortedListToBST(slow.next); // Build right subtree

        return root;
    }
}