@@ -0,0 +1,1829 @@
+/*%0A * Key point: fast/slow runner technique to find middle node, %0A *    time complexity is O(nlgn) which comes from f(n) = 2f(n/2) + cn%0A *%0A *  There is a O(n) solution that build the BST bottom-up %0A *    but it's hard to be implemented in java because of lacking passing by reference%0A */%0A%0A/**%0A * Definition for singly-linked list.%0A * public class ListNode %7B%0A *     int val;%0A *     ListNode next;%0A *     ListNode(int x) %7B val = x; next = null; %7D%0A * %7D%0A */%0A/**%0A * Definition for binary tree%0A * public class TreeNode %7B%0A *     int val;%0A *     TreeNode left;%0A *     TreeNode right;%0A *     TreeNode(int x) %7B val = x; %7D%0A * %7D%0A */%0Apublic class Solution %7B%0A    public TreeNode sortedListToBST(ListNode head) %7B%0A        if(head==null)%0A            return null;%0A        if(head.next==null)%0A            return new TreeNode(head.val);%0A        %0A        //init fast runner and slow runner    %0A        ListNode fast=head.next.next;%0A        ListNode slow=head;%0A        %0A        //partition the list from the middle, use the fast/slow runner technique%0A        //the slow pointer will be the prev of the middle node%0A        while(fast!=null && fast.next!=null)%0A        %7B%0A            fast=fast.next.next;%0A            slow=slow.next;%0A        %7D%0A        %0A        //find the middle node%0A        ListNode parent=slow.next;%0A%0A        //partition the list into left and right sublist%0A        slow.next=null;%0A        ListNode left=head;%0A        ListNode right=parent.next;%0A        parent.next=null;%0A        %0A        //make the middle node as the root, then apply the function%0A        //to the left part and the right part recursively%0A        TreeNode root=new TreeNode(parent.val);                                     %0A        root.left=sortedListToBST(left);            %0A        root.right=sortedListToBST(right);%0A        %0A        return root;%0A        %0A    %7D%0A%0A%0A%7D

Convert Sorted List to Binary Search Tree