package leetcode.convert_sorted_list_to_binary_search_tree;

import common.ListNode;
import common.TreeNode;

public class Solution {
	public TreeNode sortedListToBST(ListNode head, ListNode end) {
		if(head == end) return null;
		ListNode hare = head.next;
		ListNode tortoise = head;
		while(hare != end){
			hare = hare.next;
			if(hare != end){
				hare = hare.next;
			}
			tortoise = tortoise.next;
		}
		TreeNode root = new TreeNode(tortoise.val);
		root.left = sortedListToBST(head, tortoise);
		root.right = sortedListToBST(tortoise.next, end);
		return root;
	}
	
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null) return null;
        return sortedListToBST(head, null);
    }
    
    public static void inOrder(TreeNode node){
    	if(node != null){
    		inOrder(node.left);
    		System.err.print(node.val + " ");
    		inOrder(node.right);
    	}
    }
    
    public static void preOrder(TreeNode node){
    	if(node != null){
    		System.err.print(node.val + " ");
    		preOrder(node.left);
    		preOrder(node.right);
    	}
    }
    
    public static void main(String[] args){
    	final int N = 15;
    	ListNode[] list = new ListNode[N];
    	for(int i = 0; i < N; i++){
    		list[i] = new ListNode(i);
    		if(i > 0) list[i - 1].next = list[i];
    	}
    	
    	inOrder(new Solution().sortedListToBST(list[0]));
    	System.err.println("");
    	preOrder(new Solution().sortedListToBST(list[0]));
    	System.err.println("");
    }
}

Add java solution for 109. Convert Sorted List to Binary Search Tree
Add java solution for 109. Convert Sorted List to Binary Search Tree

109. Convert Sorted List to Binary Search Tree: https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/