有序链表转平衡 BST：快慢指针切中点
升序链表已经是中序序列。每次用快慢指针取出当前这段的中点做根，断开左半段，左右再递归。
对当前链表用快慢指针找中点做根：slow 一步、fast 两步，fast 到底时 slow 在中点。prev 切断中点前驱，左半段递归成左子树，slow.Next 递归成右子树。每次找中点线性，整棵树 O(n log n)。要 O(n) 需改成先数长度再中序填值。空间 O(log n)。
给你一个按升序排好的单链表，把它转成一棵高度平衡的二叉搜索树。平衡的意思是每个节点左右子树高度差不超过 1。升序保证中序遍历就是原来的链表顺序。
主例链表是 -10 → -3 → 0 → 5 → 9。中点是 0，做根；左边 -10、-3 建成左子树，右边 5、9 建成右子树。层序结果是 [0, -3, 9, -10, null, 5]：0 的左孩子是 -3（下面挂 -10），右孩子是 9（下面挂 5）。高度差不超过 1。
LC108 是同一题的数组版，中间元素按下标直接取。链表没有下标。本文要回答：快慢指针为什么能在单向链上取出中点，以及主例里那一次断开，断的是哪条 next。
快慢指针：两步与一步
高度平衡的 BST，根应该尽量落在有序序列的中点，左右两边人数接近。数组版 LC108 用下标 (lo+hi)/2 一次取到。链表只能顺着 next 走，随机访问这一下做不到。缺的不是「中点这个概念」，而是一个不靠下标、只靠指针移动就能停在半程的办法。
从当前这段的头出发，slow 和 fast 站在同一格。每次 slow 走一个节点，fast 走两个。fast 先撞到尾（fast 或 fast.Next 为空）时，slow 刚好走完一半，停在中点，或偶数长度时停在偏右的那个中点。这个中点的值就是当前子树的根。
根找到之后，左右两段必须变成两条独立的链表，再各自递归。所以还要一个 prev，始终跟着 slow 的前一个节点。循环结束时把 prev.Next 置空，左半段在中点处断开。不断开的话，左递归仍拿着原来的头，链上还挂着中点和右半段，会把同一段链表无限切下去。右半段的头就是 slow.Next。
用手走主例。五个节点，slow、fast 都从 -10 出发。第一步：slow 到 -3，fast 到 0。第二步：slow 到 0，fast 到 9，fast.Next 为空，停。中点是 0。prev 停在 -3，把 -3.Next 断开。左段是 -10 → -3，右段是 5 → 9。演示场景里 fast 到尾、slow 停在 0，然后画面切成左右两段，对应的就是这一刀。
左段两个节点再找中点：slow、fast 从 -10 出发，一步之后 slow 到 -3，fast 走完，-3 做根，断开后左边只剩 -10，右边为空。右段同样：5 和 9 里中点落在 9，5 做左孩子。整棵树是 0 为根，左 -3（再左 -10），右 9（再左 5）。单节点不再切，直接变成叶子；空链表返回空。
每一层，所有节点都会被快慢指针扫过一次，层数是树高，平衡时约 log n，所以总时间 O(n log n)。空间是递归栈 O(log n)。若要把时间压到 O(n)，可以先数出长度，再按中序「消费」链表：先递归左子树，当前头节点就是根，头指针前进一步，再递归右子树。那是另一条路。本页按链表当场能做的事来讲：每次切中点。
两步追一步fast 速度是 slow 的两倍，同一起点出发，fast 到终点时 slow 走了半程。偶数长度停在偏右中点，左右人数仍然相差不超过 1，平衡不破。
Go：快慢指针递归
func sortedListToBST(head *ListNode) *TreeNode {if head == nil { return nil }if head.Next == nil { return &TreeNode{Val: head.Val} }slow, fast, prev := head, head, (*ListNode)(nil)for fast != nil && fast.Next != nil {prev = slowslow = slow.Nextfast = fast.Next.Next}if prev != nil { prev.Next = nil }return &TreeNode{Val: slow.Val,Left: sortedListToBST(head),Right: sortedListToBST(slow.Next),}}
1空链返回空；只剩一个节点就当叶子，不再跑快慢指针。
2slow 一步、fast 两步。循环里 prev 始终是 slow 的前驱。
3prev.Next = nil 把左半段从中点断开。不断开，左递归会把整条链再切一遍。
4中点值做根。左递归仍从原来的 head 开始，右递归从 slow.Next 开始。主例第一刀切在 0。
总结
快慢指针取中点做根，断开左链，左右递归。主例中点 0，树是 [0,-3,9,-10,null,5]。
- 链表没有下标，取中点只能靠「一步对两步」。
- 必须切断中点前驱，否则左递归停不下来。
- 每层扫一遍链表，总时间 O(n log n)。先数长度再中序填值能做到 O(n)。