[刷题笔记] 109. Convert Sorted List to Binary Search Tree

题目

套路

首先找到中间节点mid，接下来，从head到mid之前的节点为left child，从mid节点之后到结尾为right child。

递归生成left child 和 right child 即可。

但是怎么找到中间节点呢？

这里用到了双指针技巧，即两个指针一快一慢，快指针一次前进两格，慢指针一次前进一格，这样快指针遍历到结尾的时候，慢指针就正好指向中间的位置。

def sorted_list_to_bst(head)
    return nil unless head
    if head.next == nil
        return TreeNode.new(head.val)
    end
    head = head
    mid = head
    last = head
    while last
        last = last.next
        break unless last
        first = mid
        mid = mid.next
        last = last.next
    end
    root = TreeNode.new(mid.val)
    root.right = sorted_list_to_bst(first.next.next)
    first.next = nil
    root.left = sorted_list_to_bst(head)
    return root
end