BST & LinkedList - Convert Sorted List to Binary Search Tree

LeetCode 109 - classic question of combining linkedlist and tree

# 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):
        """
        :type head: ListNode
        :rtype: TreeNode
        """
        if not head:
            return
        if not head.next:
            return TreeNode(head.val)
        
        def findMid(head):
            t = r = head
            # 1 -> 2 -> 3 -> 4 -> None
            #           t
            #                      r
            while r and r.next :
                prev  =  t
                t = t.next
                r = r.next.next
            prev.next = None
            return t
            
            
        mid = findMid(head)
        root = TreeNode(mid.val)
        root.left = self.sortedListToBST(head)
        root.right = self.sortedListToBST(mid.next)
        
        return root