Convert Sorted List to Binary Search Tree

LeetCode 109 | Difficulty: Medium

Medium

Problem Description

Given the head of a singly linked list where elements are sorted in ascending order, convert *it to a *height-balanced binary search tree.

Example 1:

Input: head = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: One possible answer is [0,-3,9,-10,null,5], which represents the shown height balanced BST.

Example 2:

Input: head = []
Output: []

Constraints:

- The number of nodes in `head` is in the range `[0, 2 * 10^4]`.

- `-10^5 <= Node.val <= 10^5`

Topics: Linked List, Divide and Conquer, Tree, Binary Search Tree, Binary Tree

---

Approach

Linked List

Use pointer manipulation. Common techniques: dummy head node to simplify edge cases, fast/slow pointers for cycle detection and middle finding, prev/curr/next pattern for reversal.

When to use

In-place list manipulation, cycle detection, merging lists, finding the k-th node.

---

Solutions

Solution 1: C# (Best: 151 ms)

Metric	Value
Runtime	151 ms
Memory	38.7 MB
Date	2022-01-14

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public TreeNode SortedListToBST(ListNode head) {
        if(head == null) return null;
    if(head.next == null) return new TreeNode(head.val);
    ListNode slow = head, pre = null, fast = head;
    while(fast != null && fast.next != null)
    {
        pre = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    pre.next = null;
    TreeNode root = new TreeNode(slow.val);
    root.left = SortedListToBST(head);
    root.right = SortedListToBST(slow.next);
    return root;
    }
}

---

Complexity Analysis

Approach	Time	Space
Linked List	$O(n)$	$O(1)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Consider: "What information do I need from each subtree?" — this defines your recursive return value.
• Draw the pointer changes before coding. A dummy head node simplifies edge cases.