https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/

convertSortedListIntoBinarySearchTree.py

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

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

class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        
        if head == None:
            return None
        
        leftTail, mid = self.middleNode(head)
        root = TreeNode(mid.val)

        rightHead = mid.next # head of right half
        mid.next = None # break list into two
        leftTail.next = None # break root off left half

        root.left = self.sortedListToBST(head) if leftTail.val != mid.val else None
        root.right = self.sortedListToBST(rightHead)

        return root


    def middleNode(self, head: ListNode) -> (ListNode, ListNode):
        slow = head
        fast = head
        beforeSlow = head
        while fast.next:
            beforeSlow = slow
            slow = slow.next
            fast = fast.next
            if fast.next:
                fast = fast.next
        return (beforeSlow, slow)