Good morning! Here's our prompt for today.

We're given a sorted singly linked list (that is, a linked list made of nodes with no pointers to the previous node) where the elements are already arranged in ascending order.

1// -9 -> -2 -> 3 -> 5 -> 9
2
3// Linked List Node Definition:
4function Node(val) {
5  this.val = val;
6  this.next = null;
7}

Can you convert it to a binary search tree?

1// Tree Node Definition
2function Node(val) {
3  this.val = val;
4  this.left = null;
5  this.right = null;
6}

Of course, there are many ways to build the BST, so any height balanced BST is acceptable. A height-balanced binary tree is just like it sounds-- the depth of the two subtrees of every node should never differ by more than 1.

Here's one tree that could be formed:

1      3
2     / \
3   -2   9
4   /   /
5 -9  5

Constraints

• Number of nodes in the linked list <= 100000
• The nodes will always contain integer values between -1000000000 and 1000000000
• Expected time complexity : O(n)
• Expected space complexity : O(n)

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

xxxxxxxxxx

​

def list_to_bst(head):

    # fill in this method

    return head

​

​

# Node definition

class TreeNode:

    def __init__(self, val):

        self.val = val

        self.left = None

        self.right = None

​

​

class LinkedListNode:

    def __init__(self, val):

        self.val = val

        self.next = None

​

​

# Regular binary trees

tree1 = TreeNode(4)

tree1.left = TreeNode(1)

tree1.right = TreeNode(3)

​

tree2 = TreeNode(5)

tree2.left = TreeNode(10)

tree2.left.left = TreeNode(17)

tree2.left.right = TreeNode(3)

tree2.right = TreeNode(8)

Here's our guided, illustrated walk-through.

How do I use this guide?