Input: head = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]

Input: head = []
Output: []

Input: head = [0]
Output: [0]

Input: head = [1,3]
Output: [3,1]

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ConvertSortedListToBinarySearchTree:
    # Convert the given linked list to an arry
    def mapListToValues(self, head: ListNode):
        vals = []
        while head:
            vals.append(head.val)
            head = head.next
        return vals
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        # check edge
        if head == None :
            return None
        if head.next == None:
            return TreeNode(head.val)
        # Form an array out of the given linked list and then
        # use the array to form the BST
        values = self.mapListToValues(head)
        # l and r represent the start and end of the given array
        def convertListToBST(l, r):
            # Invalid case
            if l > r:
                return None
            # Middle element forms the root.
            mid = (l + r) // 2
            node = TreeNode(values[mid])
            # Baes case for when there is only one element left in the array
            if l == r:
                return node
            # Recursively fom BST on the two halves
            node.left = convertListToBST(l, mid - 1)
            node.right = convertListToBST(mid + 1, r)
            return node
        return convertListToBST(0, len(values) - 1)
````
# 解法二：找链表中的中间节点，组装成二叉排序树
组装树的方法是用递归，如果能持续找到中间节点，就可以持续组装树的middle, middle.left, middle.right.
找中间节点的方法，用快慢两个指针，慢指针每次走一步，快指针每次走两步；这样子就可以找出中间节点。
```py
# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ConvertSortedListToBinarySearchTree:
    def findMiddle(self, head: ListNode):
        # The pointer used to disconnect the left half from the mid node.
        preNode = None
        slowNode = head
        fastNode = head
        # Iterate until fastNode doesn't reach the end of the linked list.
        while fastNode and fastNode.next:
            preNode = slowNode
            slowNode = slowNode.next
            fastNode = fastNode.next.next
        # Handling the case when slowNode was equal to head
        if preNode:
            preNode.next = None
        return slowNode
    def sortedListToBST2(self, head: ListNode):
        # If the head doesn't exist, then the linked list is empty
        if not head:
            return None
        # Find the middle element for the list
        mid = self.findMiddle(head)
        # the mid becones the root of the BST.
        node = TreeNode(mid.val)
        # Base case when there is just one element in the linked list
        if head == mid:
            return node
        # Recursively form balanced BSTs using the left and right halves of the original list.
        node.left = self.sortedListToBST2(head)
        node.right = self.sortedListToBST2(mid.next)
        return node

# 管理员最高权限，
$ chmod 755 *