LC109 有序链表转换二叉搜索树 · 逐题动画 · RuntimeScope

RuntimeScope/算法实验台/56 天打卡/141 题/LC109

题型地图 56天全屏 141题

当前：LC109 · 有序链表转换二叉搜索树 · 首次出现于 Day 25 · 路径：顶栏「56天打卡」→ 点击 LC 题号 → 逐题动画

← LC108 LC110 →

47 / 141回到 Day 25 卡片 141 题索引

LC109 · 有序链表转换二叉搜索树

链表版 LC108：不能随机访问 mid，怎么办？

LC108 在数组上 mid = (lo+hi)/2 是 O(1)；链表只能顺序走。主线用快慢指针找中点、prev.Next = nil 断链后递归——时间 O(n log n)。进阶可用中序模拟做到 O(n)。

-10 → -3 → 0 → 5 → 9

→ 高度平衡 BST

主线 · 链表版 LC108

· LC109 是 LC108 的链表版本：同样要把升序序列变成高度平衡 BST。
· LC108 的数组可以 O(1) 取 mid = (lo+hi)/2；链表不能随机访问，难点是如何找/模拟中点。
· 主线：快慢指针找中点 → prev.next = nil 断链 → 递归左右半段。
· 每层递归都要扫描当前链表找中点，总时间 O(n log n)，不是 O(n)。

快慢指针 + 断链 + 递归

1. slow / fast 找当前链表 mid
2. prev.Next = nil 切断左段
3. root = mid，左 = build(head)，右 = build(slow.Next)

转数组套 LC108 是 O(n) 补充思路，不在本动画主线里展开。

为什么不是 O(n)？

每一层递归都要扫描当前链表找中点（快慢指针走一遍）。
1.第 1 层：扫描 n 个节点。
2.第 2 层：左右两段各约 n/2，合计仍约 n 次指针移动。
3.共有约 log n 层，每层总扫描量同阶于 n。
4.所以总时间 = n × log n = O(n log n)，不能写成 O(n)。

进阶：中序模拟 O(n)

1.先遍历链表得到长度 n。
2.递归 build(l, r) 时，先构造左子树。
3.当前 head 就是中序序列里的 root。
4.创建 root 后执行 head = head.next。
5.再构造右子树。
6.本质：树的结构由区间大小决定，节点值按链表顺序中序填入。

1/8 · 读题 · 对比 LC108

8 步分镜：

Step 1读题 · 对比 LC108

链表版 LC108：升序链表 → 高度平衡 BST

输入是升序链表 -10 → -3 → 0 → 5 → 9。目标与 LC108 相同：生成一棵高度平衡的二叉搜索树。LC108 在数组上 mid = (lo+hi)/2 是 O(1)；链表没有下标，不能随机访问中点——这是 LC109 的额外难点。

· LC109 是 LC108 的链表版本：同样要把升序序列变成高度平衡 BST。
· LC108 的数组可以 O(1) 取 mid = (lo+hi)/2；链表不能随机访问，难点是如何找/模拟中点。
· 主线：快慢指针找中点 → prev.next = nil 断链 → 递归左右半段。
· 每层递归都要扫描当前链表找中点，总时间 O(n log n)，不是 O(n)。

为什么

LC108 的数组可以 O(1) 取 mid = (lo+hi)/2；链表不能随机访问，难点是如何找/模拟中点。

状态表 · 链表 / 指针 / 递归

视图	slow	fast	mid	断点	调用栈
全链表	—	—	—	—	[]

当前段：-10 → -3 → 0 → 5 → 9 → null

动作

读题对比 LC108：数组 O(1) 取 mid vs 链表需扫描

升序链表·快慢 / 断链·BST 构造

递归栈 · sortedListToBST

（空栈 · 建树完成）

Go · 快慢指针 + 断链递归

1func sortedListToBST(head *ListNode) *TreeNode {
2    if head == nil { return nil }
3    if head.Next == nil {
4        return &TreeNode{Val: head.Val}
5    }
6    slow, fast := head, head
7    var prev *ListNode
8    for fast != nil && fast.Next != nil {
9        prev = slow
10        slow = slow.Next
11        fast = fast.Next.Next
12    }
13    if prev != nil { prev.Next = nil }
14    root := &TreeNode{Val: slow.Val}
15    root.Left = sortedListToBST(head)
16    root.Right = sortedListToBST(slow.Next)
17    return root
18}

三种解法 · 分开写

快慢指针找中点 + 断链递归（主线）

时间 O(n log n)

空间 O(log n)

每一层递归都要用快慢指针扫描当前链表找中点；共约 log n 层，每层总扫描约 n 个节点。递归栈深度等于平衡 BST 高度，约 O(log n)。

转数组后套 LC108（补充思路）

时间 O(n)

空间 O(n)

遍历链表入数组 O(n)，再按 LC108 分治建树 O(n)。需要 O(n) 额外数组存储节点值。

进阶：中序模拟（O(n)）

时间 O(n)

空间 O(log n)

先统计长度 O(n)，再按区间递归，每个节点只访问一次。递归栈 O(log n)；用全局 head 指针按中序顺序填值。

面试回答（三段）

简单说法：我用快慢指针找到当前链表的中点作为根，然后用 prev.next = nil 把左半段切断，再递归构造左右子树。

复杂度：这个版本每层都要扫描链表找中点，总时间 O(n log n)，递归栈 O(log n)。

进阶优化：如果要求 O(n)，可以先统计链表长度，再用中序模拟构建 BST——BST 的中序遍历正好对应升序链表顺序。

常见误区

忘记 prev.next = nil

左半段没有切断时，左递归仍指向完整链表，会死循环或栈溢出。

单节点链表未特判

只有 head 一个节点时应直接 return &TreeNode{Val: head.Val}，否则 prev 为空、断链逻辑会出错。

把快慢指针分治误写成 O(n)

每层扫描一次链表，log n 层叠加才是 O(n log n)，不是「每个节点只访问一次」。

以为输出唯一

只要高度平衡且中序有序即可；右子树 [5,9] 取 5 或 9 作根都可能合法。

混淆高度平衡 BST 与 AVL

本题只要求分治后树高 O(log n)，不需要旋转维护严格 AVL。