def _toBST(self, head, tail): if head == tail: return None slow = fast = head while fast != tail and fast.next != tail: slow = slow.next fast = fast.next.next root = TreeNode(slow.val) root.left = self._toBST(head, slow) root.right = self._toBST(slow.next, tail) return root def sortedListToBST(self, head): return self._toBST(head, None) # 32 / 32 test cases passed. # Status: Accepted # Runtime: 288 ms # 57.14%
The solution does not rely on the count of nodes to determine the middle/root node in the sorted list. Instead, we can use two pointers to find out the middle case. This will cause some overhead but it quick easy to implement.