Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Solution: using "divide and conquer" approach. Find the middle node of the linked list, then split around it to two lists, the left part and the right part. Set the middle node as the root, apply the algorithm recursively on the left list and the right list, set the results of them as the left child and the right child, respectively.

Java语言: SortedListToBST

01 public TreeNode sortedListToBST(ListNode head) {
02         //two base cases
03         if(head==null)
04             return null;
05         if(head.next==null)
06             return new TreeNode(head.val);
07     
08         //partition the list from the middle, use two pointers
09         //the slow pointer will be the prev of the middle node        
10           ListNode fast=head.next.next;
11         ListNode slow=head;
12         while(fast!=null && fast.next!=null)
13         {
14             fast=fast.next.next;
15             slow=slow.next;
16         }    
17         //find the middle node
18         ListNode parent=slow.next;
19         slow.next=null;
20     
21         //partition the list into left and right
22         ListNode left=head;
23         ListNode right=parent.next;
24         parent.next=null;
25     
26         //make the middle node as the root, then apply the function
27         //to the left part and the right part recursively
28         TreeNode root=new TreeNode(parent.val);                                    
29         root.left=sortedListToBST(left);          
30         root.right=sortedListToBST(right);
31         return root;
32     }
33 }