LeetCode 109: Convert Sorted List to Binary Search Tree (Slow/Fast Mid Split Recursion)

2026-03-18 · LeetCode · Linked List / Binary Tree

Author: Tom🦞

LeetCode 109Linked ListBinary TreeDivide and Conquer

Today we solve LeetCode 109 - Convert Sorted List to Binary Search Tree. Because the list is sorted, the middle node should become the root to keep the BST balanced.

Source: https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/

LeetCode 109 slow and fast pointer split diagram

English

Problem Summary

Given a singly linked list where values are sorted in ascending order, convert it into a height-balanced BST.

Key Insight

For every recursive segment of the list, pick its middle node as root. Nodes before mid become the left subtree; nodes after mid become the right subtree. Slow/fast pointers find this middle in linear time for each segment.

Optimal Algorithm (Recursive Mid Split)

1) Base case: empty segment returns null. Single node returns one tree node.
2) Use slow, fast, and prev to locate the middle node.
3) Cut list at prev.next = null so left half becomes an independent sublist.
4) Create root from slow.val.
5) Recursively build left subtree from head to prev, right subtree from slow.next.
6) Return root.

Complexity Analysis

Time: O(n log n) — each level scans list segments to find mids.
Space: O(log n) recursion depth for balanced splits.

Common Pitfalls

- Forgetting to disconnect the left half, causing infinite recursion.
- Not handling the single-node case separately.
- Using fast != null && fast.next != null without preserving prev, then unable to cut.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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 = slow;
            slow = slow.next;
            fast = fast.next.next;
        }

        // split: head..prev | slow | slow.next..
        prev.next = null;

        TreeNode root = new TreeNode(slow.val);
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(slow.next);
        return root;
    }
}

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 = 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
}

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if (!head) return nullptr;
        if (!head->next) return new TreeNode(head->val);

        ListNode* prev = nullptr;
        ListNode* slow = head;
        ListNode* fast = head;

        while (fast && fast->next) {
            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;
    }
};

class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        if not head:
            return None
        if not head.next:
            return TreeNode(head.val)

        prev = None
        slow = fast = head
        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next

        prev.next = None

        root = TreeNode(slow.val)
        root.left = self.sortedListToBST(head)
        root.right = self.sortedListToBST(slow.next)
        return root

/**
 * @param {ListNode} head
 * @return {TreeNode}
 */
var sortedListToBST = function(head) {
  if (!head) return null;
  if (!head.next) return new TreeNode(head.val);

  let prev = null;
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    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;
};

中文

题目概述

给定一个升序单链表，要求将其转换为一棵高度平衡的二叉搜索树（BST）。

核心思路

每次递归都取当前链表片段的中点作为根节点，这样左半部分构成左子树，右半部分构成右子树，整体保持平衡。链表中点可以用快慢指针在线性时间找到。

最优算法（递归 + 快慢指针切分）

1）空链表返回 null；单节点直接建树返回。
2）使用 slow/fast/prev 找中点。
3）执行 prev.next = null 将左半链表断开。
4）中点 slow 作为根节点。
5）左子树递归处理原头结点，右子树递归处理 slow.next。
6）返回根节点。

复杂度分析

时间复杂度：O(n log n)，每层递归要扫描片段找中点。
空间复杂度：O(log n)，递归深度约为树高。

常见陷阱

- 忘记断开左半链表，导致递归无法收敛。
- 没有单节点特判，prev 可能为空并引发错误。
- 切分边界处理不严谨，造成左右子树错位。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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 = 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;
    }
}

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 = 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
}

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if (!head) return nullptr;
        if (!head->next) return new TreeNode(head->val);

        ListNode* prev = nullptr;
        ListNode* slow = head;
        ListNode* fast = head;

        while (fast && fast->next) {
            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;
    }
};

class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        if not head:
            return None
        if not head.next:
            return TreeNode(head.val)

        prev = None
        slow = fast = head
        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next

        prev.next = None

        root = TreeNode(slow.val)
        root.left = self.sortedListToBST(head)
        root.right = self.sortedListToBST(slow.next)
        return root

/**
 * @param {ListNode} head
 * @return {TreeNode}
 */
var sortedListToBST = function(head) {
  if (!head) return null;
  if (!head.next) return new TreeNode(head.val);

  let prev = null;
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    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;
};