Convert Sorted Linked List to Balanced Binary Search Tree

Given a singly linked list containing elements in strictly increasing order, your task is to convert it into a height-balanced Binary Search Tree (BST). A height-balanced BST is one where the depth of the two subtrees of every node never differs by more than one. This conversion is useful in scenarios where you need to efficiently search or manipulate ordered data structures by leveraging the logarithmic time complexity of BST operations.

Problem Description

You are provided with the head of a singly linked list. Each node in the list contains an integer value, and the list is guaranteed to be sorted in strictly increasing order. Your goal is to construct a Binary Search Tree from this linked list such that the resulting BST is height-balanced.

Requirements:

The Binary Search Tree must satisfy the properties of a BST: for any given node, all values in its left subtree are strictly less than the node's value, and all values in its right subtree are strictly greater than the node's value.
The resulting Binary Search Tree must be height-balanced. This means that for every node in the tree, the height difference between its left and right subtrees is at most 1.
You should create new TreeNode objects for the BST; do not modify the existing linked list nodes directly into tree nodes (though you can reuse their values).

Edge Cases:

An empty linked list should result in an empty BST (represented as null or an equivalent representation for an empty tree).
A linked list with a single node should result in a BST with a single root node.

Examples

Example 1:

Input: Head of linked list: -10 -> -3 -> 0 -> 5 -> 9
Output:
      0
     / \
   -3   9
   /   /
 -10  5

Explanation: The middle element `0` becomes the root. The left half `[-10, -3]` forms the left subtree, and the right half `[5, 9]` forms the right subtree. This process is recursively applied to the sub-lists to ensure balance.

Example 2:

Input: Head of linked list: 1 -> 3
Output:
    3
   /
  1

Explanation: For an even number of elements, either of the two middle elements can be chosen as the root. Here, `3` is chosen, and `1` forms its left child. Alternatively, `1` could be the root with `3` as its right child, and both would be valid balanced BSTs.

Example 3:

Input: Head of linked list: (empty)
Output: null

Explanation: An empty linked list results in an empty BST.

Constraints

The number of nodes in the linked list will be between 0 and 10^5.
The values in the linked list will be integers.
The linked list is guaranteed to be sorted in strictly increasing order.
The solution should aim for optimal time and space complexity.

Notes

To efficiently construct a balanced BST from a sorted sequence, consider selecting the middle element of the sequence as the root of the current subtree. This naturally divides the remaining elements into two roughly equal halves, which will form the left and right subtrees.
You'll need to define a TreeNode structure (or class) with value, left, and right pointers/references.
Think about how to efficiently find the middle element of a linked list, or how to adapt an approach that doesn't require explicit middle finding if you convert the list to an array-like structure first.

Convert Sorted Linked List to Balanced Binary Search Tree

Problem Description

Requirements:

The Binary Search Tree must satisfy the properties of a BST: for any given node, all values in its left subtree are strictly less than the node's value, and all values in its right subtree are strictly greater than the node's value.

The resulting Binary Search Tree must be height-balanced. This means that for every node in the tree, the height difference between its left and right subtrees is at most 1.

You should create new TreeNode objects for the BST; do not modify the existing linked list nodes directly into tree nodes (though you can reuse their values).

Edge Cases:

An empty linked list should result in an empty BST (represented as null or an equivalent representation for an empty tree).

A linked list with a single node should result in a BST with a single root node.

Examples

Example 1:

Input: Head of linked list: -10 -> -3 -> 0 -> 5 -> 9 Output: 0 / \ -3 9 / / -10 5 Explanation: The middle element `0` becomes the root. The left half `[-10, -3]` forms the left subtree, and the right half `[5, 9]` forms the right subtree. This process is recursively applied to the sub-lists to ensure balance.

Example 2:

Input: Head of linked list: 1 -> 3 Output: 3 / 1 Explanation: For an even number of elements, either of the two middle elements can be chosen as the root. Here, `3` is chosen, and `1` forms its left child. Alternatively, `1` could be the root with `3` as its right child, and both would be valid balanced BSTs.

Example 3:

Input: Head of linked list: (empty) Output: null Explanation: An empty linked list results in an empty BST.

Notes

To efficiently construct a balanced BST from a sorted sequence, consider selecting the middle element of the sequence as the root of the current subtree. This naturally divides the remaining elements into two roughly equal halves, which will form the left and right subtrees.

You'll need to define a TreeNode structure (or class) with value, left, and right pointers/references.

Think about how to efficiently find the middle element of a linked list, or how to adapt an approach that doesn't require explicit middle finding if you convert the list to an array-like structure first.