# Share my JAVA solution, 1ms, very short and concise.

• ``````public class Solution {
}
public TreeNode toBST(ListNode head, ListNode tail){

while(fast!=tail&&fast.next!=tail){
fast = fast.next.next;
slow = slow.next;
}
}
``````

}

• Another solution

``````public class Solution {
private ListNode next;
int height=0;
while(next!=null) {
height++;
next = next.next;
}
return recur(height);
} private TreeNode recur(int n){
if(n==0) return null;
if(n==1){
TreeNode x = new TreeNode(next.val);
next = next.next;
return x;
}
TreeNode temp = new TreeNode(0);
temp.left = recur(n/2);
temp.val=next.val;
next=next.next;
temp.right=recur((n-1)/2);
return temp;
}
``````

}

• that's very clever! Thank you. I've always to use rotate to implement it, but it's trivial and hard to realize

• Awesome solution!

• Is every "thead" is the Penultimate node before tail?why not mediumz?

• sorry i miss what you mean

• The time complexity of the solution is O(n logn) since you have to traverse the sub-list in each recursive call.

• I had the same idea, and I find this way better than the others which were counting lengths and stuff.

• @JosephTao What is the running time for this solution?

• I run your code, but it can not pass some exams,like[1,2,3,4,5] :(

• There is TLE.

• Same idea!
No need to check whether the head is null in sortedListToBST, it'll make the codes a little bit consier : )

• @PriyamSirohi a wrong solution

• @cifer-lee Shows accepted for me!

• tail? This is ingenious ðŸ˜Š

• Copy pasted your code and did not work.
Changing

``````while(fast!=tail && fast.next!=tail)
``````

to

``````while(fast!=tail && fast.next!=tail && fast.next.next!=tail)
``````

works for simple cases, but got TLE for larger ones.

• Very clever! No need to change original List for divide-and-conquer. Thanks!

• This post is deleted!

• Says time limit exceeded on a lot of solutions. Trying to figure out what actually works.

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