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.

解法一：双节点

public TreeNode sortedListToBST(ListNode head) {
    if(head == null)
        return null;
    ListNode fast = head;
    ListNode slow = head;
    ListNode prev =null; 
    while(fast != null && fast.next != null)
    {
        fast = fast.next.next;
        prev =slow;
        slow=slow.next;
    }
    TreeNode root = new TreeNode(slow.val);
    if(prev != null)
        prev.next = null; //断掉前面序列和中点之间的联系，不然recursion没法找到前面序列的中点
    else
        head  = null;

    root.left = sortedListToBST(head);
    root.right = sortedListToBST(slow.next);
    return root;
}

reference：https://leetcode.com/discuss/58428/recursive-construction-using-slow-fast-traversal-linked-list

解法二：

 1 public class Solution {
 2     private ListNode current;
 3 
 4     private int getListLength(ListNode head) {
 5         int size = 0;
 6 
 7         while (head != null) {
 8             size++;
 9             head = head.next;
10         }
11 
12         return size;
13     }
14 
15     public TreeNode sortedListToBST(ListNode head) {
16         int size;
17 
18         current = head;
19         size = getListLength(head);
20 
21         return sortedListToBSTHelper(size);
22     }
23 
24     public TreeNode sortedListToBSTHelper(int size) {
25         if (size <= 0) {
26             return null;
27         }
28 
29         TreeNode left = sortedListToBSTHelper(size / 2);
30         TreeNode root = new TreeNode(current.val);
31         current = current.next;
32         TreeNode right = sortedListToBSTHelper(size - 1 - size / 2);
33 
34         root.left = left;
35         root.right = right;
36 
37         return root;
38     }
39 }

reference：http://www.jiuzhang.com/solutions/convert-sorted-list-to-binary-search-tree/