Problem

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

Example
               2
1->2->3  =>   / \
             1   3

思路

1. 找到中点的上一个点
2. 拆分成两个list
3. 转化这两个list
4. 然后合并成新的tree

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

        if (head.next == null) {
            return new TreeNode(head.val);
        }

        if (head.next.next == null) {
            TreeNode n1 = new TreeNode(head.val);
            n1.right = new TreeNode(head.next.val);
            return n1;
        }

        ListNode midPrev = findMidPrev(head);
        ListNode mid = midPrev.next;
        ListNode l2 = mid.next;
        midPrev.next = null;
        mid.next = null;

        TreeNode root = new TreeNode(mid.val);
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(l2);

        return root;
    }

    private ListNode findMidPrev(ListNode head) {
        ListNode curt = head;
        int len = 0;
        while (curt != null) {
            curt = curt.next;
            len++;
        }
        int k = len % 2 == 0 ? len/2 - 1 : len/2;
        for (int i = 1; i < k; i++) {
            head = head.next;
        }
        return head;
    }

Optimization

• fast & slow pointer to find mid.

public TreeNode sortedListToBST(ListNode head) {
    if(head==null) return null;
    return toBST(head,null);
}
public TreeNode toBST(ListNode head, ListNode tail){
    ListNode slow = head;
    ListNode fast = head;
    if(head==tail) return null;

    while(fast!=tail&&fast.next!=tail){
        fast = fast.next.next;
        slow = slow.next;
    }
    TreeNode thead = new TreeNode(slow.val);
    thead.left = toBST(head,slow);
    thead.right = toBST(slow.next,tail);
    return thead;
}