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

第一反应就是用快慢指针找链表中点！！！然而这个方法还是使用的不熟练，不知道应该怎么设置终止条件！！！

还是要反复练习！！！

一般情况，slow和fast指针都指向head节点，while循环条件为fast != null && fast.next != null！！！

corner case有：
1）head==null，直接判断，一般是直接返回null即可。
2）head.next == null，即链表中仅一个元素。此时由于fast指针一开始指向head，若仅一个head元素，则fast无法连续往后跳2格！！！因此也许特别考虑。

本题还有一个trick的地方在于，循环结束slow指针指向中点后，还需要将slow前一个指针prev设置为prev.next = null，即切断链表前半段与slow的联系！！！

如何实现？！

开始就采用一个prev指针，设为null，每次slow向后移动，prev也向后移动！！！

有一点要注意，若prev一直为null，说明链表中只有一个head元素，并没有进入while循环移动快慢指针！！！

代码：

public class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        ListNode prev = null;
        ListNode slow = head, fast = head;
        
        // find the median node in the linked list, after executing this loop 
        // fast will pointing to the last node, while slow is the median node.
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            prev = slow;
            slow = slow.next;
        }
        
        if (prev != null) prev.next = null;
        else head = null;
        
        TreeNode node = new TreeNode(slow.val);
        node.left = sortedListToBST(head);
        node.right = sortedListToBST(slow.next);
        return node;
    }
    

}

参考：

https://discuss.leetcode.com/topic/8141/share-my-o-1-space-and-o-n-time-java-code/4