1 /** 2  * Definition for singly-linked list. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { val = x; next = null; } 7  * } 8  */ 9 /**10  * Definition for binary tree11  * public class TreeNode {12  *     int val;13  *     TreeNode left;14  *     TreeNode right;15  *     TreeNode(int x) { val = x; }16  * }17  */18 public class Solution {19     public TreeNode sortedListToBST(ListNode head) {20         if (head==null)21             return null;22         23         ListNode end = head;24         while (end.next!=null){25             end = end.next;26         }27         TreeNode root = sortedListToBSTRecur(head,end);28         29         return root;30     }31     32     //Convert the list from head to end into BST, return the root node33     public TreeNode sortedListToBSTRecur(ListNode head, ListNode end){34         //If only one node.35         if (head==end){36             TreeNode root = new TreeNode(head.val);37             return root;38         }39         40         //If only two node.41         if (head.next==end){42             TreeNode root = new TreeNode(head.val);43             TreeNode child = new TreeNode(end.val);44             root.right = child;45             return root;46         }47         48         49         //Otherwise, count the number of node in the list, find out the median one, 50         //and convert the left list and right list to BST.51         int nodeNum = 1;52         ListNode curNode = head;53         while (curNode!=end){54             curNode = curNode.next;55             nodeNum++;56         }57         int mid = nodeNum/2+nodeNum%2;58         ListNode median = null;59         ListNode pre = null;60         curNode = head;61         //NOTE: we only need to move (mid-1) steps to move curNode to the median one.62         for (int i=0;i<mid-1;i++){63             pre = curNode;64             curNode = curNode.next;65         }66         median = curNode;67         TreeNode root = new TreeNode(median.val);68         TreeNode leftChild = sortedListToBSTRecur(head,pre);69         TreeNode rightChild = sortedListToBSTRecur(median.next,end);70         root.left = leftChild;71         root.right = rightChild;72         return root;73     }74 }