难度: 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 <= 105运行时间: 80 ms
内存: 17.9 MB
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def sortedListToBST(self, head: ListNode) -> TreeNode:
if head is None:
return None
if head.next is None:
return TreeNode(head.val)
f = head
s = head
pre = None
while f and f.next:
f = f.next.next
pre = s
s = s.next
pre.next = None
right = s.next
root = TreeNode(s.val)
root.left = self.sortedListToBST(head)
root.right = self.sortedListToBST(right)
return root
这个题解的思路是使用快慢指针找到链表的中点，然后递归地将左右两个子链表转换为左右子树。具体步骤如下： 1. 如果链表为空，直接返回None；如果链表只有一个节点，则直接返回这个节点为根的树。 2. 使用快慢指针找到链表的中点，慢指针每次走一步，快指针每次走两步，当快指针走到末尾时，慢指针指向中点。 3. 将中点的值作为根节点的值，然后递归地将中点左边的链表转换为左子树，中点右边的链表转换为右子树。 4. 返回根节点。
时间复杂度: O(nlogn)
空间复杂度: O(n)
class Solution:
def sortedListToBST(self, head: ListNode) -> TreeNode:
if head is None:
return None
if head.next is None:
return TreeNode(head.val)
# 使用快慢指针找到链表的中点
f = head
s = head
pre = None
while f and f.next:
f = f.next.next
pre = s
s = s.next
# 将中点左边的链表断开
pre.next = None
right = s.next
# 创建根节点，递归构建左右子树
root = TreeNode(s.val)
root.left = self.sortedListToBST(head)
root.right = self.sortedListToBST(right)
return root
在使用快慢指针策略时，慢指针（s）始终指向中点或中点附近的节点，而快指针（f）以两倍速度移动。当快指针到达链表末尾时，慢指针就位于中间位置。对于偶数节点的链表，此方法将导致慢指针停留在中间两个节点的第一个。通过在慢指针前维护一个指针（pre），我们可以在找到中点后将链表从中点前一个节点断开，从而将链表分为两部分。这样，即使是偶数个节点，链表也总是被分割成两个几乎等长的部分，左边包含中点前的所有节点，右边包含中点后的所有节点。
`pre` 变量的作用是跟踪慢指针（s）的前一个节点。这是必要的，因为一旦找到中点，我们需要将链表从中点前一个节点断开，以便递归构造左子树。如果没有`pre`，我们无法断开链表。快指针（f）以两倍的速度移动，而慢指针（s）以一倍速度移动，因此当快指针达到链表末尾时，慢指针恰好达到整个链表的中间位置。在偶数节点的情况下，这种方法使慢指针指向中间两个节点的第一个，而在奇数节点的情况下，慢指针正好指向中点。
当链表为空时，没有节点可以转换为二叉搜索树，因此返回`None`是合理的，表示树为空。当链表只有一个节点时，这个节点本身就可以直接成为二叉搜索树的根节点，因为没有其他节点与之比较，它自然满足二叉搜索树的要求（即根节点大于左子树中的所有节点且小于右子树中的所有节点）。这种处理逻辑简化了递归调用，因为它处理了递归的基本情况，避免了进一步的递归，从而提高了效率并简化了代码。