一、题目
1、算法题目
“给定单链表头结点，其中元素升序排序，将其转换为高度平衡的二叉搜索树。”
题目链接：
来源：力扣（LeetCode）
2、题目描述
给定一个单链表的头节点 head ，其中的元素 按升序排序 ，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。
网络异常，图片无法展示
|
示例 1： 输入: head = [-10,-3,0,5,9] 输出: [0,-3,9,-10,null,5] 解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树。 复制代码
示例 2： 输入: head = [] 输出: [] 复制代码
二、解题
1、思路分析
这道题跟108题类似，第一步都是需要确定根节点，也就是让左右子树的节点个数尽可能接近，这样左右子树的高度就会相近。
这样的根节点被称为中位数，如果链表的元素个数为奇数，那么中间值就位中位数，如果元素个数为偶数，那么两个中间值都可以作为中位数。
根据中位数的性质，可以使用分治的思路，递归地对左右子树进行构造，找出对应的中位数作为根节点，这样得到的二叉搜索树就是平衡的。
2、代码实现
代码参考：
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; } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(n log n)
其中n是链表的长度。
空间复杂度： O(log n)
其中n是数组的长度，空间复杂度取决于递归栈的深度，递归栈的深度是O(log n)。
三、总结
找出链表中位数节点的方法有很多，比较简单的是使用双指针，在开始时候两个指针都指向左端点left。
然后第一个指针向右移动两次的同时第二个指针向右移动一次，直到第一个指针到达边界的时候，第二个指针对应的元素就是中位数。
找到中位数之后，将其作为当前根节点的元素，然后递归地构造其左侧部分的链表对应的左子树，以及右侧部分的链表对应的右子树。
