Problem

We are given a sorted singly linked list where elements are in ascending order. The task is to convert this linked list to a height balanced Binary Search Tree (BST).

Here, a height-balanced binary tree can be defined as a binary tree in which the depth of the two subtrees of every node never differs by more than 1.

For example, if we are given the sorted linked list: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

1
2
3      0
4     / \
5   -3   9
6   /   /
7 -10  5

Approach

The efficient solution to this problem is to use the method of binary cutting, same as found in Binary Search method. We can find the middle element of the linked list and make it a root of the BST. Then do the same thing for the left half and right half of the linked list recursively.

Steps

1. If the head node is NULL, the BST is also NULL. Return NULL.
2. If the next node of head is NULL, then the BST is a single node with the value the same as head, return this tree.
3. Use a helper function findMid(head) to find the middle node in the linked list.
   1. Initialize two pointer fast, slow pointing to head node.
   2. Using fast-slow (tortoise and the hare) pointer algorithm, move the fast pointer by 2 and slow pointer by 1 till the end of the linked list.
   3. Now, slow pointer will be pointing to middle of the list. Cut the linked list from the middle (for this, we also kept a record of the node before middle, prev)
4. The root of the tree will be node at the middle.
5. Recursively construct the left subtree, root->left = sortedListToBST(head).
6. Recursively construct the right subtree, root->right = sortedListToBST(mid->next).
7. The tree with root as root node is the required BST.

Solution

Java

1
2java
3class Solution {
4    public TreeNode sortedListToBST(ListNode head) {
5        if (head == null)
6            return null;
7        if (!head.next)
8            return new TreeNode(head.val);
9
10        ListNode mid = findMid(head);
11        TreeNode root = new TreeNode(mid.val);
12        root.left = sortedListToBST(head);
13        root.right = sortedListToBST(mid.next);
14
15        return root;
16    }
17
18    private ListNode findMid(ListNode head) {
19        ListNode prev = null;
20        ListNode slow = head;
21        ListNode fast = head;
22
23        while (fast && fast.next) {
24            prev = slow;
25            slow = slow.next;
26            fast = fast.next.next;
27        }
28        prev.next = null;
29
30        return slow;
31    }
32}

Python

1
2python
3class Solution:
4    def sortedListToBST(self, head):
5        if not head:
6            return None
7        if not head.next:
8            return TreeNode(head.val)
9            
10        prev, mid = self.findMid(head)
11        root = TreeNode(mid.val)
12        prev.next = None
13        root.left = self.sortedListToBST(head)
14        root.right = self.sortedListToBST(mid.next)
15        
16        return root
17        
18    def findMid(self, head):
19        prev = None
20        slow, fast = head, head
21        
22        while fast and fast.next:
23            prev = slow
24            slow, fast = slow.next, fast.next.next
25        
26        return prev, slow

C++

1
2cpp
3class Solution {
4public:
5    TreeNode* sortedListToBST(ListNode* head) {
6        if (head == nullptr)
7            return nullptr;
8            
9        if (!head->next)
10            return new TreeNode(head->val);
11        
12        ListNode* mid = findMid(head);
13        TreeNode* root = new TreeNode(mid->val);
14        root->left = sortedListToBST(head);
15        root->right = sortedListToBST(mid->next);
16
17        return root;
18    }
19
20private:
21    ListNode* findMid(ListNode* head) {
22        ListNode* prev = nullptr;
23        ListNode* slow = head;
24        ListNode* fast = head;
25
26        while (fast && fast->next) {
27            prev = slow;
28            slow = slow->next;
29            fast = fast->next->next;
30        }
31        prev->next = nullptr;
32        
33        return slow;
34    }
35};

JavaScript

1
2javascript
3class Solution {
4    sortedListToBST(head) {
5        if(head === null) 
6            return null;
7            
8        if(head.next === null) 
9            return new TreeNode(head.val);
10
11        let mid = this.findMid(head);
12        let root = new TreeNode(mid.val);
13        root.left = this.sortedListToBST(head);
14        root.right = this.sortedListToBST(mid.next);
15        
16        return root;
17    }
18
19    findMid(head) {
20        let prev = null;
21        let slow = head;
22        let fast = head;
23
24        while(fast !== null && fast.next !== null) {
25            prev = slow;
26            slow = slow.next;
27            fast = fast.next.next;
28        }
29        prev.next = null;
30        
31        return slow;
32    }
33}

C#

1
2csharp
3public class Solution {
4    public TreeNode SortedListToBST(ListNode head) {
5        if (head == null)
6            return null;
7            
8        if (head.next == null)
9            return new TreeNode(head.val);
10        
11        ListNode mid = FindMid(head);
12        TreeNode root = new TreeNode(mid.val);
13        root.left = SortedListToBST(head);
14        root.right = SortedListToBST(mid.next);
15
16        return root;
17    }
18
19    private ListNode FindMid(ListNode head) {
20        ListNode prev = null;
21        ListNode slow = head;
22        ListNode fast = head;
23
24        while (fast != null && fast.next != null) {
25            prev = slow;
26            slow = slow.next;
27            fast = fast.next.next;
28        }
29        prev.next = null;
30        
31        return slow;
32    }
33}

Here we have provided the solutions in Python, JavaScript, Java, and C++ languages for converting a sorted linked list to a balanced Binary Search Tree (BST). These solutions all follow the same algorithm and method. They all create a function that finds the middle element of the linked list and uses that as the starting point for creating the BST.

They establish the base cases by checking if the linked list is empty, or has only one node. And then they find the middle node, set that as the root of the BST, and recursively create left and right sub-trees using the portions of the linked list before and after the middle node.

While the languages have different syntax, the same fundamental logic is applied across all solutions. For instance, unlike languages like Python and JavaScript, C++ requires explicit memory allocation for new nodes (new TreeNode()); yet, the core logic is identical.

Although C# is not specified in the question, it is included as it is a common language in use. It follows the same procedural format as Java and C++, but utilizes C# syntax.

Performance may vary slightly based on the language/platform chosen, considering differences in memory management, function calls, etc. However, the time complexity of this implementation should generally be O(N log N), as we are essentially performing a binary search and constructing a binary tree. We could improve time complexity to O(N) by converting linked list to array and then recursively picking middle elements for left and right sub-trees.

Let's validate these solutions with sample inputs and analyze for edge cases for completeness. Remember an efficient solution not only resolves the problem but should also handle potential edge cases.

In conclusion, these solutions provide an effective methodology to construct a balanced BST from a sorted linked list across multiple programming languages. This problem is seen regularly in technical interviews and coding assessments. It's a great problem for demonstrating understanding of linked lists, binary trees, and the concept of recursion.