How do I find the middle node in a sorted linked list for BST conversion?

Use the slow and fast pointer technique where slow moves one step and fast moves two steps; slow will point to the middle node when fast reaches the end.

What happens if the list has an even number of nodes?

Choose the second of the two middle nodes to maintain height balance consistently, preventing left-heavy or right-heavy trees in recursive construction.

Can I use extra arrays instead of pointer manipulation?

While possible, using extra arrays increases space complexity and violates the efficient pointer manipulation pattern expected for this problem, reducing memory efficiency.

How does GhostInterview handle empty lists?

It recognizes an empty list and returns a null root, ensuring recursive calls terminate correctly without null pointer exceptions.

Why is pointer manipulation critical for this problem?

Pointer manipulation avoids copying sublists, preserves original nodes, reduces space usage, and maintains the sorted order and height-balance required for BST correctness.

#109

Medium

auto_awesome链表指针操作

LeetCode 题解工作台

有序链表转换二叉搜索树

给定一个单链表的头节点 head ，其中的元素按升序排序，将其转换为平衡二叉搜索树。示例 1: 输入: head = [-10,-3,0,5,9] 输出: [0,-3,9,-10,null,5] 解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索…

链表分治树二叉搜索树二叉树

题目描述

给定一个单链表的头节点 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 * 10⁴] 范围内
-10⁵ <= Node.val <= 10⁵

lightbulb

解题思路

方法一：DFS

我们先将链表转换为数组 $\textit{nums}$ ，然后使用深度优先搜索构造二叉搜索树。

我们定义一个函数 $\textit{dfs}(i, j)$ ，其中 $i$ 和 $j$ 表示当前区间为 $[i, j]$ 。每次我们选择区间中间位置 $\textit{mid}$ 的数字作为根节点，递归地构造左侧区间 $[i, \textit{mid} - 1]$ 的子树，以及右侧区间 $[\textit{mid} + 1, j]$ 的子树。最后返回 $\textit{mid}$ 对应的节点作为当前子树的根节点。

在主函数中，我们只需要调用 $\textit{dfs}(0, n - 1)$ 并返回即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是链表的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

# 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: Optional[ListNode]) -> Optional[TreeNode]:
        def dfs(i: int, j: int) -> Optional[TreeNode]:
            if i > j:
                return None
            mid = (i + j) >> 1
            l, r = dfs(i, mid - 1), dfs(mid + 1, j)
            return TreeNode(nums[mid], l, r)

        nums = []
        while head:
            nums.append(head.val)
            head = head.next
        return dfs(0, len(nums) - 1)

speed

复杂度分析

指标	值
时间	complexity depends on the approach: splitting lists recursively is O(n log n), whereas inorder simulation achieves O(n). Space complexity is O(log n) due to recursion stack in a balanced BST. Using pointer manipulation avoids extra arrays, reducing overhead compared to naive list copying, making this solution memory-efficient while maintaining height balance.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you correctly find the middle node without extra list creation?
question_mark
Can you maintain pointer integrity while recursively constructing left and right subtrees?
question_mark
Will you handle empty and single-node lists without causing null pointer errors?

warning

常见陷阱

外企场景

error
Failing to disconnect the left sublist causes cycles or incorrect subtree connections.
error
Using list slicing instead of pointer manipulation increases space and breaks the O(n) expectation.
error
Incorrect middle selection in even-length lists can unbalance the BST or violate height-balance requirement.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Convert Sorted Array to BST (array-based version with direct index access).
arrow_right_alt
Balanced BST to Sorted Linked List (reverse pattern requiring inorder traversal).
arrow_right_alt
Convert Sorted Circular Linked List to BST (requires handling circular pointer traversal).

help

常见问题

外企场景

继续练习

#108 将有序数组转换为二叉搜索树 #106 从中序与后序遍历序列构造二叉树 #105 从前序与中序遍历序列构造二叉树