Recursive Java solution


  • 1
    G
    public TreeNode sortedListToBST(ListNode head) {
            // base case
            if(head==null) return null;
            if(head.next==null) {
                TreeNode root = new TreeNode(head.val);
                return root;
            }
    
            // find the mid using slow and fast pointer
            ListNode slow = head, fast = head, pre = null;
            while(fast!=null && fast.next!=null) {
                pre = slow;
                slow = slow.next;
                fast = fast.next.next;
            }
    
            // slow is the mid, should be the root
            // head to pre nodes belong to root.left
            // slow.next nodes belong to root.right
            pre.next = null;
            fast = slow.next;
            TreeNode root = new TreeNode(slow.val);
            root.left = sortedListToBST(head);
            root.right = sortedListToBST(fast);
            
            return root;
     }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.