[LeetCode] Convert Sorted List to Binary Search Tree

Convert Sorted List to Binary Search Tree

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

解题思路：
找到中间点，然后左边就为其左子树，右边部分就为其右子树。
1. 找中间点，可以先扫描一遍list, 然后得出node的总数n, 然后n/2就是其中间点
2. 可以用两个pointer, 一个每次走1一步，另一个每次走2步。等走2步的pointer到达尾部时，走一步的pointer刚好走到中间位置。由于我们要找到中间位置的pointer. 所以我们找到了中间pointer的前一个node。

Java Code:

public TreeNode sortedListToBST(ListNode head) {
        if(head == null) return null;
        ListNode safehead = new ListNode(0);
        safehead.next = head;
        
        ListNode prev = safehead;
        ListNode p = head;
        
        while( p != null && p.next != null){
            p = p.next.next;
            prev = prev.next;
        }
            
        TreeNode root = new TreeNode(prev.next.val);
        p = prev.next.next;
        prev.next = null;
        root.left = sortedListToBST(safehead.next);
        root.right = sortedListToBST(p);
            
        return root;
    }