LeetCode 109. Sorted Linked List Conversion Binary Search Tree

原题网址：https://leetcode.cn/problems/convert-sorted-list-to-binary-search-tree/

The ordered linked list is transformed into a highly balanced binary search tree.

有序,高度平衡,So it is divided from the middle of the linked list,形成树,The idea of ​​merging is used

    // It has to be a highly balanced binary search tree.The seats must be separated by the midpoint of the linked list.
    // 由于是有序的,So traverse the linked list,After adding one by one, it is still a linked list structure,不行.

    public TreeNode sortedListToBST(ListNode head) {
    
        return mergeListToBST(head,null);

    }
    // Note that the interval here is left closed and right open
    private TreeNode mergeListToBST(ListNode head, ListNode tail) {
    
        // 遍历完了链表,因为是左闭右开的区间
        if(head == tail) {
    
            return null;
        }
        // This is only one element
        if(head.next == tail) {
    
            return new TreeNode(head.val);
        }

        ListNode midNode = getMidNode(head,tail);
        TreeNode root = new TreeNode(midNode.val);
        root.left  = mergeListToBST(head,midNode);
        root.right = mergeListToBST(midNode.next,tail);
        return root;
    }

    private ListNode getMidNode(ListNode head, ListNode tail) {
    
        ListNode fast = head;
        ListNode slow = head;
        while(fast != tail && fast.next != tail) {
    
            fast= fast.next.next;
            slow= slow.next;
        }
        return slow;

    }