Leetcode - Converted Sorted List to BST

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

[分析]
思路1复杂度是O（nlogn），实现过程中发现自己二指针法一开始是写错的，错误的结果是二分后左边会比右边多两个元素，在Reorder List中这种写法之所以也能被Accept完全是凑巧，因为多两个不影响结果~
思路2：参考https://leetcode.com/discuss/23676/share-my-o-1-space-and-o-n-time-java-code 相比于Convert Sorted Array to Binary Search Tree难点是不能常数时间内找到链表的中间节点，此题有助于加深对中序遍历的理解。

public class Solution {
    // Method 2: O(N)
    private ListNode curr;
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        int n = 0;
        ListNode p = head;
        while (p != null) {
            n++;
            p = p.next;
        }
        curr = head;
        return inorder(1, n);
    }
    public TreeNode inorder(int l, int r) {
        if (l > r)
            return null;
        int mid = l + (r - l) / 2;
        TreeNode left = inorder(l, mid - 1);
        TreeNode root = new TreeNode(curr.val);
        root.left = left;
        curr = curr.next;
        root.right = inorder(mid + 1, r);
        return root;
    }
    
    // Method 1: O(NlogN)
    public TreeNode sortedListToBST1(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return new TreeNode(head.val);
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode slow = dummy, fast = head;
        while (fast.next != null) {
            fast = fast.next;
            if (fast.next != null) {
                slow = slow.next;
                fast = fast.next;
            }
        }
        ListNode mid = slow.next;
        TreeNode root = new TreeNode(mid.val);
        root.right = sortedListToBST(mid.next);
        if (mid != head) {
            slow.next = null;
            root.left = sortedListToBST(head);
        }
        return root;
    }
}