Leetcode 109.有序链表转换二叉搜索树（Medium）

给定一个单链表的头节点  head ，其中的元素 按升序排序 ，将其转换为 平衡 二叉搜索树。

示例 1:

输入: head = [-10,-3,0,5,9]
输出: [0,-3,9,-10,null,5]
解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树。

示例 2:

输入: head = []
输出: []

提示:

• head 中的节点数在[0, 2 * 104] 范围内
• -105 <= Node.val <= 10

思路：先获取到链表的长度，然后去递归构造树即可，每次构造的树节点永远是链表或子链表的中心，但是由于是单向链表，所以每次获取链表中的节点的时候就会导致每次都从头开始，可以用循环链表改善，如果要构造的节点的坐标大于length/2的时候就next length -index次，然后递归构造，设置临界条件即可，若length为0就是无节点，如果length为1就是叶子节点。然后上代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    ListNode temp;
    public TreeNode sortedListToBST(ListNode head) {
        temp = head;
        // 思路就是取链表的中心节点，作为总树或子树的根节点，然后循环、递归
        int length = getListLength(head);
        return buildTree(0, length);
        
    }
    
    
    public TreeNode buildTree(int start ,int length) {
        int i = 0;
        ListNode t = temp;
        while (i < start + length/2) {
            t = t.next;
            i++;
        }
        
        // 如果是0，直接为null
        if (length == 0) return null;
        
        // 如果length为1的时候，直接返回，因为它已经是树叶节点了
        if (length == 1) return new TreeNode(t.val, null, null);
        
        // 遍历到中心节点，就构造节点
        return new TreeNode(t.val, buildTree(start, length/2), buildTree(start + length/2 +1, length-1-length/2));
        
    }
    

    // 获取节点总节点数
    public int getListLength(ListNode head) {
        int length = 0;
        while(head != null) {
            length++;
            head = head.next;
        }
        return length;
    }
    
}

快慢指针也是解决中间值问题的一个快速的解决办法，思路相同，只是取中间值的方法不同。

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        return buildTree(head, null);
    }

    public TreeNode buildTree(ListNode left, ListNode right) {
        if (left == right) {
            return null;
        }
        ListNode mid = getMedian(left, right);
        TreeNode root = new TreeNode(mid.val);
        root.left = buildTree(left, mid);
        root.right = buildTree(mid.next, right);
        return root;
    }

    public ListNode getMedian(ListNode left, ListNode right) {
        ListNode fast = left;
        ListNode slow = left;
        while (fast != right && fast.next != right) {
            fast = fast.next;
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}