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

 

思路：二分法；

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } *//** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public TreeNode sortedListToBST(ListNode head) {        if (head==null)                              //如果一开始传进来的是空链表，返回null            return null;        if (head.next==null)                      //递归终止条件            return new TreeNode(head.val);        ListNode p = head,q = head,m = head;    //快慢指针找中间值        while (q!=null&&q.next!=null){            q = q.next.next;            p = p.next;        }        q = p.next;        TreeNode root = new TreeNode (p.val);        while (m.next!=p)                                                m = m.next;                           m.next = null;        root.left = sortedListToBST(head);            //分治        root.right = sortedListToBST(q);        return root;            }}