I used an extra array to do this, it has O(n) storage and time.
But I have a feeling that this one can be solved with O(1) memory, of course, linear time.
Can someone do this in place with O(n) time?

The key is to create the nodes by the list's order in a bottomup fashion. Read this article:
Convert Sorted List to Balanced Binary Search Tree (BST) for an indepth analysis and solution for this problem.

Here is my python code with the same idea as others said.
class Solution: # @param head, a list node # @return a tree node def sortedListToBST(self, head): if not head: return None N = 0 cur = head while cur: N += 1 cur = cur.next A = self.listToBST(head, N) return A[0] def listToBST(self, head, N): if N == 1: return [TreeNode(head.val), head.next] l = self.listToBST(head, N/2) root = TreeNode(l[1].val) root.left = l[0] if (N1)/2: r = self.listToBST(l[1].next, (N1)/2) root.right = r[0] return [root, r[1]] else: return [root, l[1].next]

The above code is so elegant but tricky. To understand the code, u can read this one http://www.geeksforgeeks.org/sortedlinkedlisttobalancedbst/ which contain a better explanation.