[Leecode] Convert Sorted List to Binary Search Tree

Problem statement: 
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Solution:
1. Two pointers - fast and slow to find the middle point of linked list (notice the handling at the middle part as well as the fast pointer)
2. Recurse on the left half and the right half of the linked list

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def sortedListToBST(self, head): """ :type head: ListNode :rtype: TreeNode """ # base case if not head: return None if not head.next: return TreeNode(head.val) # find the middle pointer fast = head.next slow = head while fast and fast.next and fast.next.next: slow = slow.next fast = fast.next.next # slow is the end of the left, slow.next is root, slow.next.next is right lroot = slow.next lright = slow.next.next slow.next = None # recursion on the first half and the second half root = TreeNode(lroot.val) right = self.sortedListToBST(lright) left = self.sortedListToBST(head) root.left, root.right = left, right return root