/109. Convert Sorted Linked List to Height-Balanced BST

109. Convert Sorted Linked List to Height-Balanced BST

Medium

Linked Lists66.1% acceptance

Given the head node of a singly linked list with integer values sorted in ascending order, construct a height-balanced binary search tree (BST) containing the same values. Return the root node of the BST. The BST must be height-balanced, meaning the depths of the two subtrees of every node differ by no more than one. The BST should be represented as a TreeNode object, where each node contains an integer value, a left child, and a right child. If the input list is empty, return None.

Example 1

Input: ListNode(1, ListNode(2, ListNode(3, ListNode(4))))

Output: TreeNode(3, TreeNode(2, TreeNode(1)), TreeNode(4))

Explanation: BST root is 3, left subtree is 2->1, right subtree is 4.

Example 2

Input: ListNode(-5, ListNode(-2, ListNode(0, ListNode(7, ListNode(10)))))

Output: TreeNode(0, TreeNode(-5, None, TreeNode(-2)), TreeNode(10, TreeNode(7), None))

Explanation: BST root is 0, left subtree is -5->-2, right subtree is 10->7.

Constraints

0 <= number of nodes in input_list <= 20000
-100000 <= node_value <= 100000
Input list is sorted in strictly ascending order

Python (current runtime)

Case 1

Input: ListNode(8, ListNode(12, ListNode(15)))

Expected: TreeNode(12, TreeNode(8), TreeNode(15))

Case 2

Input: ListNode(-1, ListNode(0, ListNode(1, ListNode(2, ListNode(3, ListNode(4))))))

Expected: TreeNode(2, TreeNode(0, TreeNode(-1), TreeNode(1)), TreeNode(4, TreeNode(3), None))

Case 3

Input: None

Expected: None