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;
}
Share my O(1) space and O(n) time Java code


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

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

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

Great solution! It traverses the list
twice
: the first time to get thelength
, the second time forinorder 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 + (rightleft)/2; TreeNode* leftnode = inorderRe(head, left, mid1); TreeNode* cur = new TreeNode(head>val); cur>left = leftnode; head = head>next; cur>right = inorderRe(head, mid+1, right); 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 { 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; } }