Convert a singly linked list to BST
Filed under Qualcomm
Free read 1 of 3Confirm the input is a sorted singly linked list and the output must be a height-balanced BST.
The question
Given the head of a singly linked list where elements are sorted in ascending order, convert it to a height-balanced Binary Search Tree (BST). A height-balanced BST is a binary tree in which the depth of the two subtrees of every node never differs by more than one.
Constraints
- The number of nodes is in the range [0, 2 * 10^4].
- Node values are between -10^5 and 10^5.
- The linked list is sorted in ascending order.
Examples
- Input
- head = [-10,-3,0,5,9]
- Output
- [0,-3,9,-10,null,5]
- Why
- One possible valid height-balanced BST is shown. [0,-10,5,null,-3,null,9] is also acceptable.
Approach
Confirm the input is a sorted singly linked list and the output must be a height-balanced BST.
Convert the linked list into an array in O(N) time, then use a standard recursive array-to-BST algorithm.
Use the slow and fast pointer technique to find the middle node of the list to serve as the root, then recurse.
Handle null head (return null) and single-node lists (return the node as a tree leaf).
Solution
O(N log N) time, O(log N) space
class ListNode: # Linked List Node
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class TreeNode: # Tree Node
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def sortedListToBST(self, head: ListNode) -> TreeNode:
if not head: return None
if not head.next: return TreeNode(head.val)
# Find middle using slow/fast pointers
prev, slow, fast = None, head, head
while fast and fast.next:
prev = slow
slow = slow.next
fast = fast.next.next
# Disconnect left half
if prev: prev.next = None
root = TreeNode(slow.val)
root.left = self.sortedListToBST(head)
root.right = self.sortedListToBST(slow.next)
return root
Tips
- What they are testing: Test with an empty list, a single node, and a list with an even number of nodes to ensure the middle selection is robust.
- Common mistake: Failing to disconnect the left half of the linked list when using a recursive approach, leading to infinite loops or incorrect tree structure.
Related Qualcomm questions
Collected from public candidate posts and coding forums. Updated Nov 2026.