Convert Sorted List to Binary Search Tree

The key idea is to find the mid node and handle left part and right part separately.

time complexity O(nlogn):

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
        """

        return self.myToBST(head, None)


    def myToBST(self, head, tail):

        fast = head
        slow = head
        if head == tail:
            return None


        while fast != tail and fast.next != tail:
            fast = fast.next.next
            slow = slow.next

        node = TreeNode(slow.val)
        node.right = self.myToBST(slow.next, tail)
        node.left = self.myToBST(head, slow)
        return node

time complexity O(n) -- like inorder traversal

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
        """
        if not head:
            return None

        size = 0
        self.cur = head
        cur = head

        while cur:
            cur = cur.next
            size += 1

        return self.myToBST(0, size-1)


    def myToBST(self, start, end):
        if start > end:
            return None

        mid = start + (end-start)/2
        left = self.myToBST(start, mid-1)
        node = TreeNode(self.cur.val)

        node.left = left
        self.cur = self.cur.next
        right = self.myToBST(mid+1, end)
        node.right = right

        return node