Share My Easy Understatnd Java Solution.


  • 21
    A
    public class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if(head==null)
            return null;
        ListNode slow = head;
        ListNode fast = head;
        ListNode temp=null;
        
        //find the mid node
        while(fast.next!=null && fast.next.next!=null){
            fast = fast.next.next;
            temp = slow;
            slow = slow.next;
        }
        
        if(temp!=null)
            temp.next = null; //break the link
        else
            head = null;
            
        TreeNode root = new TreeNode(slow.val);
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(slow.next);
        return root;
    }
    

    }


  • 0
    G

    IMHO, you can't modify the original list unless you are allowed to do so


  • 0
    H

    I think your temp will never equal to null.
    Sorry, I got it.


  • 0
    A

    when the list's size is 1


  • 0
    P

    Is it O(N^2) time complexity?


  • 14
    D

    It's possible to accomplish without modifying the original list.

    We are already finding the middle node which is the end for the left subtree. So pass on this node recursively instead of breaking the list.

    public TreeNode sortedListToBST(ListNode head) {
    	return sortedListToBST(head, null);
    }
    
    private TreeNode sortedListToBST(ListNode start, ListNode end) {
    
    	if (start == null || start == end)
    		return null;
    
    	ListNode fast = start;
    	ListNode slow = start;
    
    	while (fast.next != end && fast.next.next != end) {
    		fast = fast.next.next;
    		slow = slow.next;
    	}
    	
    	TreeNode root = new TreeNode(slow.val);
    	root.left = sortedListToBST(start, slow);
    	root.right = sortedListToBST(slow.next, end);
    
    	return root;
    }

  • 0
    D

    This is the best solution so far. Thanks


  • 0
    J

    Best solution ever!


Log in to reply
 

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