Share my O(1) space and O(n) time Java code


  • 138
    T
    private ListNode node;
    
    public TreeNode sortedListToBST(ListNode head) {
    	if(head == null){
    		return null;
    	}
    	
    	int size = 0;
    	ListNode runner = head;
    	node = head;
    	
    	while(runner != null){
    		runner = runner.next;
    		size ++;
    	}
    	
    	return inorderHelper(0, size - 1);
    }
    
    public TreeNode inorderHelper(int start, int end){
    	if(start > end){
    		return null;
    	}
    	
    	int mid = start + (end - start) / 2;
    	TreeNode left = inorderHelper(start, mid - 1);
    	
    	TreeNode treenode = new TreeNode(node.val);
    	treenode.left = left;
    	node = node.next;
    
    	TreeNode right = inorderHelper(mid + 1, end);
    	treenode.right = right;
    	
    	return treenode;
    }

  • 38
    V

    I think since you use recursive methods call, so the space complexity is O(log n) instead of O(1) since the recursive call stack will also cost space.


  • 9
    T

    Thanks for you reminder. I think usually we discuss the space complexity is based on heap space rather than stack space.


  • 31
    H

    Hi! Just a little confusion here. Your solution should be O(n), but it doesn't run consistently faster than my O(nlgn) solution. Any thoughts on the reason? Awesome solution btw:)

    public TreeNode sortedListToBST(ListNode head) {
                // base case
                if (head == null) return null;
        
                ListNode slow = head;
                ListNode fast = head;
                ListNode prev = null;
                // find the median node in the linked list, after executing this loop
                // fast will pointing to the last node, while slow is the median node.
                while (fast.next != null) {
                    fast = fast.next;
                    if (fast.next == null) {
                        break;
                    }
                    fast = fast.next;
                    prev = slow;
                    slow = slow.next;
                }
                if (prev != null) prev.next = null;
                else head = null;
        
                TreeNode root = new TreeNode(slow.val);
                root.left = sortedListToBST(head);
                root.right = sortedListToBST(slow.next);
        
                return root;
            }

  • 2
    H

    may be test with very long lists? O(n) can be slower than O(nlgn) for small inputs.


  • 0
    A

    i think the code may not compile, you must declare "node" somewhere, it's missing.


  • 0
    A

    what is the node here?


  • 4
    T

    Hi, the node is declared at the first line.


  • 1
    T

    At the first line: private ListNode node;


  • 3

    I share the same idea with hanzhou87, but in my solution, prev is not needed:

    class Solution {
    public:
        TreeNode* sortedListToBST(ListNode* head) {
            if (head == NULL)
                return NULL;
            if (head->next == NULL)
                return new TreeNode(head->val);
            ListNode *fast = head->next->next, *slow = head;
            while (fast != NULL && fast->next != NULL) {
                slow = slow->next;
                fast = fast->next->next;
            }
            TreeNode* root = new TreeNode(slow->next->val);
            root->right = sortedListToBST(slow->next->next);
            slow->next = NULL;
            root->left = sortedListToBST(head);
            return root;
        }
    };

  • 14
    H

    My Java recursive solution (node tail is excluded):

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

    }


  • 1
    D

    For sortedListToBST function conditions check, you can only have if (head == tail) return null; instead of if(head == null || head == tail)
    return null;
    if(head.next == tail)
    return new TreeNode(head.val);


  • 1
    D

    Very great idea any way, thanks.


  • 0
    W
    This post is deleted!

  • 6
    M

    Great solution! It traverses the list twice: the first time to get the length, the second time for inorder reconstruction. O(n) time

    Personally, I prefer this one than the other answers here which walk through the list every time to find the middle point. O(nlgn) time

    If I made a mistake, please figure it out. Welcome to comment. Rewrite in C++

    class Solution {
    public:
        TreeNode* sortedListToBST(ListNode* head) {
            if(head == NULL) return NULL;
            ListNode* cnt = head;
            int len = 1;
            while(cnt->next != NULL){
                cnt = cnt->next;
                len++;
            }
            return inorderRe(head, 1, len);
        }
        
        TreeNode* inorderRe(ListNode*& head, int left, int right) { //pass head by reference
            if(left>right) return NULL;
            int mid = left + (right-left)/2;
            
            TreeNode* leftnode = inorderRe(head, left, mid-1);
            
            TreeNode* cur = new TreeNode(head->val);
            cur->left = leftnode;
            
            head = head->next;
            
            cur->right = inorderRe(head, mid+1, right);
            return cur;
        }
    };

  • 2
    R

    Here is similar solution where list state is stored in a parameter instead of a field which I believe makes it a thread safe implementation:

    public class Solution {
        private static class State {
            ListNode head;
            State(ListNode head) {
                this.head = head;
            }
        }
        public TreeNode sortedListToBST(ListNode head) {
            return sortedListToBST(size(head), new State(head));
        }
        private TreeNode sortedListToBST(int size, State state) {
            if (size<=0) return null;
            int mid = size/2;
            TreeNode root = new TreeNode(0);
            root.left = sortedListToBST(mid, state);
            root.val = state.head.val;
            state.head = state.head.next;
            root.right = sortedListToBST(size - mid - 1, state);
            return root;
        }
        private int size(ListNode head) {
            int size = 0;
            while (head != null) {
                head = head.next;
                size++;
            }
            return size;
        }
    }
    

  • 0
    R

    Very nice solution! The space complexity is O(log(N)) though.


  • 0
    P

    hi, thanks for your solution. I implemented in the similar way, but used TreeNode head as the parameter to sortedListToBST(int size, TreeNode head) instead of sortedListToBST(int size, State state). However it does not work.. Is there any reason that you use the State?


  • 1
    S

    I think space complexity is still O(n) as you need to create n TreeNode objects anyway.


  • 0
    H

    I support this solution. Clear and easy to read.


Log in to reply
 

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