Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example: Given the sorted linked list: [-10,-3,0,5,9], One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

class Solution {
    private ListNode findMiddle (ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next;
        ListNode preSlow = null;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            preSlow = slow;
            slow = slow.next;
        }
        if(preSlow != null) preSlow.next = null;
        return slow;
    }

    public TreeNode sortedListToBST(ListNode head) {
        if(head == null) return null;
        if(head.next == null) return new TreeNode(head.val);
        ListNode middle = findMiddle(head);
        ListNode head2 = middle.next;
        middle.next = null;
        TreeNode root = new TreeNode(middle.val);
        if (middle != head) { //很重要 当middle就是head时候表示一共只有两个node 
        //左边那个又是middle又是head 已经当成middle被拿去作为root了 就不能再用作head搜索一次
            root.left = sortedListToBST(head);
        }

        root.right = sortedListToBST(head2);

        return root;
    }
}


Method 1: root to leaf 和array to bst思路一样

public class Solution {

    private TreeNode toBSTHelper(ListNode head, ListNode tail) {
       if(head == tail) return null;

        ListNode slow = head;
        ListNode fast = head.next;


        while(fast != tail && fast.next != tail) {
            slow = slow.next;
            fast = fast.next.next;
        }

        TreeNode root = new TreeNode(slow.val);
        root.left = toBSTHelper(head, slow);
        root.right = toBSTHelper(slow.next, tail);

        return root;
    }

    public TreeNode sortedListToBST(ListNode head) {
        if(head == null) return null;
        return toBSTHelper(head, null);
    }   
}


Method 2: leaf to root 对list进行逆中序遍历操作 左中右

public class Solution {
    private ListNode current;

    private int getListLength(ListNode head) {
        int size = 0;

        while (head != null) {
            size++;
            head = head.next;
        }

        return size;
    }

    public TreeNode sortedListToBST(ListNode head) {
        int size;

        current = head;
        size = getListLength(head);

        return sortedListToBSTHelper(size);
    }

    public TreeNode sortedListToBSTHelper(int size) {
        if (size <= 0) {
            return null;
        }

        TreeNode left = sortedListToBSTHelper(size / 2);
        TreeNode root = new TreeNode(current.val);
        current = current.next;
        TreeNode right = sortedListToBSTHelper(size - 1 - size / 2);

        root.left = left;
        root.right = right;

        return root;
    }
}