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，直接为nullif (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;}
}