# Java solution using two pointer technique

1. Move to the middle of the linked list using 'slow' and 'fast' pointers. Also keep a 'previous' pointer pointing to a node before 'slow'
2. Add 'slow' value to BST
3. To divide the list into two parts, make previous.next = null
4. Call the same function with head node again
5. Call the same function with slow.next

Below is the code :-

``````public class Solution {
TreeNode root = null;
public TreeNode sortedListToBST(ListNode head) {
subListProcess(head);
return root;
}

void subListProcess(ListNode head) {
if(head == null)
return;
ListNode slow = head, fast = head, previous = null;
while(fast != null && fast.next != null) {
previous = slow;
slow = slow.next;
fast = fast.next.next;
}
root = insertInBST(slow.val, root);
if(previous != null) {
previous.next = null;
subListProcess(head);
}
subListProcess(slow.next);
}

TreeNode insertInBST(int val, TreeNode root) {
if(root == null)
return new TreeNode(val);
if(val < root.val)
root.left = insertInBST(val, root.left);
else
root.right = insertInBST(val, root.right);
return root;
}
}
``````
1. Time taken to get to the middle of the list : n/2, which is O(n)
2. Above process is done logn time.
3. To insert into BST, O(logn)

So, overall, O(n(logn)^2). Please clarify if there is some mistake in time complexity calculation.

• I shrank your code and it's still easy to understand.

``````public TreeNode sortedListToBST(ListNode head) {
if(head==null){
return null;
}else if(head.next==null){
return new TreeNode(head.val);
}
ListNode prev=null,cur=head,runner=head;
while(runner!=null && runner.next!=null){
prev=cur;
cur=cur.next;
runner=runner.next.next;
}
TreeNode root=new TreeNode(cur.val);
if(prev!=null){
prev.next=null;
root.left=sortedListToBST(head);
}
root.right=sortedListToBST(cur.next);
return root;
}``````

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