1+ /*
2+ Author: King, wangjingui@outlook.com
3+ Date: Dec 12, 2014
4+ Problem: Convert Sorted List to Binary Search Tree
5+ Difficulty: Medium
6+ Source: https://oj.leetcode.com/problems/convert-sorted-list-to-binary-search-tree/
7+ Notes:
8+ Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
9+
10+ Solution: Recursion. Pre-order. O(n)
11+ */
12+ /**
13+ * Definition for singly-linked list.
14+ * public class ListNode {
15+ * int val;
16+ * ListNode next;
17+ * ListNode(int x) { val = x; next = null; }
18+ * }
19+ */
20+ /**
21+ * Definition for binary tree
22+ * public class TreeNode {
23+ * int val;
24+ * TreeNode left;
25+ * TreeNode right;
26+ * TreeNode(int x) { val = x; }
27+ * }
28+ */
29+ public class Solution {
30+ public TreeNode sortedListToBST (ListNode head ) {
31+ return sortedListToBSTRe (head ,null );
32+ }
33+ public TreeNode sortedListToBSTRe (ListNode start ,ListNode end ) {
34+ if (start ==end )return null ;
35+ ListNode pre =null ;
36+ ListNode slow =start ;
37+ ListNode fast =start ;
38+ while (fast !=end &&fast .next !=end ) {
39+ fast =fast .next .next ;
40+ slow =slow .next ;
41+ }
42+ TreeNode node =new TreeNode (slow .val );
43+ node .left =sortedListToBSTRe (start ,slow );
44+ node .right =sortedListToBSTRe (slow .next ,end );
45+ return node ;
46+ }
47+ public TreeNode sortedListToBST_2 (ListNode head ) {
48+ if (head ==null )return null ;
49+ if (head .next ==null )return new TreeNode (head .val );
50+ ListNode slow =head ;
51+ ListNode fast =head ;
52+ ListNode pre =null ;
53+ while (fast .next !=null &&fast .next .next !=null ) {
54+ pre =slow ;
55+ slow =slow .next ;
56+ fast =fast .next .next ;
57+ }
58+ fast =slow .next ;
59+ TreeNode node =new TreeNode (slow .val );
60+ if (pre !=null ) {
61+ pre .next =null ;
62+ node .left =sortedListToBST (head );
63+ }
64+ node .right =sortedListToBST (fast );
65+ return node ;
66+ }
67+ }
