Easy Python : using prev node


  • 0
    A
    class Solution(object):
        def sortedListToBST(self, head):
            """
            :type head: ListNode
            :rtype: TreeNode
            """
            if not head:
                return None
            if not head.next:
                return TreeNode(head.val)
                
            slow, fast = head, head
            prev = slow
            while fast and fast.next:
                prev = slow
                slow = slow.next
                fast = fast.next.next
            
            node = slow # current mid node
            next = node.next
            prev.next = None # disconnect the prev half list
            node.next = None # disconnect the next half list
            
            treeNode = TreeNode(node.val)
            treeNode.left = self.sortedListToBST(head)
            treeNode.right = self.sortedListToBST(next)
            return treeNode
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.