public class Solution {
public TreeNode sortedListToBST(ListNode head) {
// 2:40pm  3:05pm
if (head == null) {
return null;
}
ListNode mid = head;
ListNode fast = head;
ListNode preMid = null;
while (fast != null && fast.next != null && fast.next.next != null) {
preMid = mid;
mid = mid.next;
fast = fast.next.next;
}
TreeNode root = new TreeNode(mid.val);
if (preMid != null) {
preMid.next = null;
root.left = sortedListToBST(head);
}
root.right = sortedListToBST(mid.next);
return root;
}
}
Java 1ms solution: O(nlogn) time, O(1) space


I make the mid node as root, and construct the left subtree from nodes before the mid node, and the right subtree from the nodes following root. Therefore, the fast and mid are just the same as code that you use to find the mid node.
For the left subtree, knowing the head is not enough, since I need to cut off the connection from premid to mid, by setting premid.next = null; And that is why I need to know premid.
since it is a singly linked list!