Convert Sorted List to Balanced BST

You are given a sorted singly linked list. Your task is to convert it into a height-balanced binary search tree (BST). A BST is height-balanced if the depth of the two subtrees of every node never differs by more than 1.

The conversion should preserve the in-order traversal of the BST so that the resulting sequence is identical to the input sorted list. Specifically, if the linked list is given as \(1 \to 2 \to 3 \to \cdots \to n\), then the in-order traversal of your BST should yield \(1, 2, 3, \dots, n\).

Note: Use the two-pointer technique (slow and fast pointers) to find the middle element of the list as the root of the BST.

inputFormat

The first line contains an integer n denoting the number of nodes in the linked list. The second line contains n space-separated integers which are sorted in ascending order.

outputFormat

Output the in-order traversal of the constructed balanced BST. The numbers should be printed in a single line separated by a single space.

7
1 2 3 4 5 6 7

1 2 3 4 5 6 7