京公网安备11010502063487号给定一个升序链表，构造一棵高度平衡的二叉搜索树。标准做法是用快慢指针找到链表中点当根，中点左右两段分别递归构造左右子树。一个真实会犯的错误是：找到中点后，忘了把中点前一个结点的 next 指针断开——这样递归处理左半部分时，传进去的链表其实还连着后面所有结点，根本不会在中点停下，每一层递归都会重新定位到同一个中点，导致无限递归崩溃。本文用真实反例验证这个错误，给出正确写法、5 种语言实现，以及快慢指针找中点的分步演示。
本文只用自己的话概括题意，完整约束以官方页面为准。给定一个升序链表，构造一棵高度平衡的二叉搜索树（本题允许多种正确答案）。一共 5 组用例，覆盖：官方示例、空链表、单结点、两结点、七结点：
[-10, -3, 0, 5, 9] → [0,-3,9,-10,null,5] [] → [] [1] → [1] [1, 2] → [2,1] [1, 2, 3, 4, 5, 6, 7] → [4,2,6,1,3,5,7]
这题的标准做法是用快慢指针找到链表中点当根，中点左边的部分递归构造左子树，右边的部分递归构造右子树。一个真实会犯的错误是：找到中点后，忘了把"中点前一个结点"的 next 指针断开（设成 None）。这一步很容易被漏掉，因为不断开链表在逻辑上"看起来"也没错——中点左边那一段的起点依然是 head。但递归处理左半部分时，传进去的还是原来的 head，如果没有断开，这个 head 开始的链表其实一直连到链表末尾，根本不会在中点处停下：
输入链表 -10→-3→0→5→9\n正确写法（找到中点后断开 prev.next） → [0,-3,9,-10,null,5]\n陷阱写法（忘了断开 prev.next） → 程序崩溃：RecursionError（无限递归）
陷阱写法会直接触发递归深度超限——因为左子树的递归调用每次看到的都是"断点前那一段没有真正断开"的同一条链表，每一层递归都会在同样的位置重新找到同一个中点，永远无法收敛到空链表这个终止条件，是真正的死循环而不是慢一点。这一步"断开"是让递归能正常终止的必要条件，不是可有可无的优化。
用快指针一次走两步、慢指针一次走一步找到链表中点，同时用 prev 记住中点前一个结点；找到后立刻把 prev.next 设成空，断开左右两半；中点的值作为根，左半部分（head 开始，到断开处为止）递归构造左子树，右半部分（slow.next 开始）递归构造右子树。时间 O(n log n)（每层都要重新走一遍慢快指针），空间 O(log n)（递归栈）。Python、Java、Go、JavaScript、C++ 都是真实编译运行的，用同一组 5 个测试用例。
Python · 解法代码def sorted_list_to_bst(head): if head is None: return None if head.next is None: return TreeNode(head.val) prev, slow, fast = None, head, head while fast and fast.next: # 快慢指针找中点，prev 记录中点前一个结点 prev = slow slow = slow.next fast = fast.next.next prev.next = None # 关键一步：把左半部分和中点断开 root = TreeNode(slow.val) root.left = sorted_list_to_bst(head) root.right = sorted_list_to_bst(slow.next) return root
$ python3 solution.py [-10, -3, 0, 5, 9] → [0,-3,9,-10,null,5] [] → [] [1] → [1] [1, 2] → [2,1] [1, 2, 3, 4, 5, 6, 7] → [4,2,6,1,3,5,7]
Java · 解法代码class Solution { public TreeNode sortedListToBST(ListNode head) { if (head == null) return null; if (head.next == null) return new TreeNode(head.val); ListNode prev = null, slow = head, fast = head; while (fast != null && fast.next != null) { // 快慢指针找中点，prev 记录中点前一个结点 prev = slow; slow = slow.next; fast = fast.next.next; } prev.next = null; // 关键一步：把左半部分和中点断开 TreeNode root = new TreeNode(slow.val); root.left = sortedListToBST(head); root.right = sortedListToBST(slow.next); return root; } }
$ javac -d build Main.java && java -cp build Main [-10, -3, 0, 5, 9] → [0,-3,9,-10,null,5] [] → [] [1] → [1] [1, 2] → [2,1] [1, 2, 3, 4, 5, 6, 7] → [4,2,6,1,3,5,7]
Go · 解法代码func sortedListToBST(head *ListNode) *TreeNode { if head == nil { return nil } if head.Next == nil { return &TreeNode{Val: head.Val} } var prev *ListNode slow, fast := head, head for fast != nil && fast.Next != nil { // 快慢指针找中点，prev 记录中点前一个结点 prev = slow slow = slow.Next fast = fast.Next.Next } prev.Next = nil // 关键一步：把左半部分和中点断开 root := &TreeNode{Val: slow.Val} root.Left = sortedListToBST(head) root.Right = sortedListToBST(slow.Next) return root }
$ go run solution.go [-10, -3, 0, 5, 9] → [0,-3,9,-10,null,5] [] → [] [1] → [1] [1, 2] → [2,1] [1, 2, 3, 4, 5, 6, 7] → [4,2,6,1,3,5,7]
JavaScript · 解法代码function sortedListToBST(head) { if (head === null) return null; if (head.next === null) return new TreeNode(head.val); let prev = null, slow = head, fast = head; while (fast && fast.next) { // 快慢指针找中点，prev 记录中点前一个结点 prev = slow; slow = slow.next; fast = fast.next.next; } prev.next = null; // 关键一步：把左半部分和中点断开 const root = new TreeNode(slow.val); root.left = sortedListToBST(head); root.right = sortedListToBST(slow.next); return root; }
$ node run.js [-10, -3, 0, 5, 9] → [0,-3,9,-10,null,5] [] → [] [1] → [1] [1, 2] → [2,1] [1, 2, 3, 4, 5, 6, 7] → [4,2,6,1,3,5,7]
C++ · 解法代码class Solution { public: TreeNode* sortedListToBST(ListNode* head) { if (!head) return nullptr; if (!head->next) return new TreeNode(head->val); ListNode *prev = nullptr, *slow = head, *fast = head; while (fast && fast->next) { // 快慢指针找中点，prev 记录中点前一个结点 prev = slow; slow = slow->next; fast = fast->next->next; } prev->next = nullptr; // 关键一步：把左半部分和中点断开 TreeNode* root = new TreeNode(slow->val); root->left = sortedListToBST(head); root->right = sortedListToBST(slow->next); return root; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin [-10, -3, 0, 5, 9] → [0,-3,9,-10,null,5] [] → [] [1] → [1] [1, 2] → [2,1] [1, 2, 3, 4, 5, 6, 7] → [4,2,6,1,3,5,7]
共 5 组用例（含边界），以 Python 结果为基准逐组比对：\n Python 通过 5/5\n Java 通过 5/5\n Go 通过 5/5\n JavaScript 通过 5/5\n C++ 通过 5/5
Python 版本另外做了一次针对"快慢指针找中点 + 递归"写法本身的随机验证：对每一棵构造出来的树，检查是不是高度平衡，以及中序遍历回去是不是能精确还原原链表。
随机验证 5,000 组（链表长度 0 到 60 的随机升序链表），构造出的树全部满足「高度平衡」且「中序遍历还原原链表」，0 组不满足。
另外四种语言只在上面 5 组固定用例上验证过，没有做大规模随机验证。
下面的演示用官方示例链表 -10→-3→0→5→9：每一步用快慢指针找到当前段的中点，把中点前一个结点的 next 断开，中点值作为根，左右两段分别递归构造左右子树。蓝色是快慢指针正在扫描的位置，绿色是已经放进树里的结点。每一帧都是把上面的解法在这组输入上真实执行记录下来的。