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

• ``````private ListNode node;

return null;
}

int size = 0;

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

• 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.

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

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

TreeNode root = new TreeNode(slow.val);
root.right = sortedListToBST(slow.next);

return root;
}``````

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

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

• what is the node here?

• Hi, the node is declared at the first line.

• At the first line: private ListNode node;

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

``````class Solution {
public:
return NULL;
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;
return root;
}
};``````

• My Java recursive solution (node tail is excluded):

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

}

• For sortedListToBST function conditions check, you can only have if (head == tail) return null; instead of if(head == null || head == tail)
return null;

• Very great idea any way, thanks.

• This post is deleted!

• 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:
int len = 1;
while(cnt->next != NULL){
cnt = cnt->next;
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);

cur->left = leftnode;

return cur;
}
};``````

• 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 {
}
}
}
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.right = sortedListToBST(size - mid - 1, state);
return root;
}
int size = 0;
size++;
}
return size;
}
}
``````

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

• 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?

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

• I support this solution. Clear and easy to read.

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