Convert Sorted List to BST

Question

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Thoughts

跟将一个sorted array convert to BST思路差不多，但是这里是linked list

1 找到中点 2 recursively construct 左子树和右子树

Solution

"""
Definition of ListNode
class ListNode(object):

    def __init__(self, val, next=None):
        self.val = val
        self.next = next

Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""
class Solution:
    """
    @param head: The first node of linked list.
    @return: a tree node
    """
    def length(self, head):
        length = 0
        while head:
            length += 1
            head = head.next
        return length

    def convert(self, head, length):
        if not head or length == 0:
            return None
        if length == 1:
            return TreeNode(head.val)
        mid = length / 2

        """
        找到中点，要经历mid-1个
        """
        pre = head
        i = 1
        while i < mid:
            i += 1
            pre = pre.next

        """
        长度为奇数偶数的差别
        """
        if length % 2 == 0:
            #length is even
            leftLen = mid - 1
            rightLen = length - mid
        else:
            #length is odd
            pre = pre.next
            leftLen = mid
            rightLen = length - mid - 1
        root = TreeNode(pre.val)
        root.left = self.convert(head, leftLen)
        root.right = self.convert(pre.next, rightLen)
        return root


    def sortedListToBST(self, head):
        # write your code here
        if not head:
            return None
        length = self.length(head)
        return self.convert(head, length)