[LeetCode] Convert Sorted List to Binary Search Tree

Problem:
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
Solution1:O(n^2)

public class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null)
            return null;
        if(head.next == null)
            return new TreeNode(head.val);
            
        ListNode midNode = findMid(head);
        TreeNode root = new TreeNode(midNode.val);
        root.right = sortedListToBST(midNode.next);
        ListNode tmp = head;
        if(tmp == midNode)
            head = null;
        else{
            while(tmp.next != midNode){
                tmp = tmp.next;
            }
            tmp.next = null;
        }
        root.left = sortedListToBST(head);
        return root;
    }
    ListNode findMid(ListNode head){
        if(head.next == null || head.next.next == null)
            return head;
        ListNode slow = head;
        ListNode faster = head;
        while(faster!=null &&  faster.next!=null){
            slow = slow.next;
            faster = faster.next.next;
        }
        return slow;
    }
}

Solution2:O(nlogn)

public class Solution {
    public class Dao{
        ListNode n;
        TreeNode t;
        public Dao(ListNode n, TreeNode t){
            this.n=n;
            this.t=t;
        }
    }    
    
    public TreeNode sortedListToBST(ListNode head) {
        ListNode temp = head;
        int length = 0;
        while(temp!=null){
            temp=temp.next;
            length++;
        }
        return (sortedListToBST(head,0,length-1)).t;
    }
    
    public Dao sortedListToBST(ListNode head, int start, int end){
        if(start>end)
            return new Dao(head,null);
        
        int mid=(start+end)/2;
        Dao leftChild = sortedListToBST(head, start,mid-1); 
        head = leftChild.n;
        TreeNode parent = new TreeNode(head.val);       
        parent.left=leftChild.t;
        head = head.next;
        Dao rightChild = sortedListToBST(head, mid+1,end);
        parent.right = rightChild.t;
        return new Dao(rightChild.n,parent);
    }
}

Key Concept: Using Dao to hold listnode and treenode