LeetCode 109. 有序链表转换二叉搜索树

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        return partition(head, getLength(head));
    }

    public int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }

    public TreeNode partition(ListNode head, int length) {
        if (length == 0) return null;
        if (length == 1) return new TreeNode(head.val);
        int mid = length / 2 - 1;
        ListNode node = head;
        for (int i = 0; i < mid; i++) {
            node = node.next;
        }
        ListNode now = node.next;
        node.next = null;
        TreeNode tree = new TreeNode(now.val);
        int newLen = mid + 1;
        tree.left = partition(head, newLen);
        tree.right = partition(now.next, length - newLen - 1);
        return tree;
    }
}