[leetcode] ordered linked list transformation binary search tree

#LeetCode A daily topic 【 Special topic of linked list 】

• Ordered list transform binary search tree
  https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/
• analysis
  This problem has a train of thought immediately ：
  Find the midpoint of the linked list 、 Cut into two linked lists , Construct trees , The left node of the tree points to the left part of the linked list , The right node of the tree points to the right part of the linked list , And then recursive processing .
  One thing to note is that ： When the linked list is divided into two parts , Take the midpoint as the root node of the tree . I made this mistake before , Take the midpoint as the root node of the tree , Have put the midpoint in the right linked list , The result is redundant data .
• Realization

public TreeNode sortedListToBST(ListNode head) {
    
        if (head == null) {
    
            return null;
        }
        if (head.next == null) {
    
            return new TreeNode(head.val);
        }
        //  routine , Three pointers to find the midpoint of the linked list ,pre Is the midpoint ,slow To the right of the midpoint 
        ListNode slow = head, fast = head, prev = null;
        while (fast != null && fast.next != null) {
    
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        //  To the right of the midpoint  slow
        //  To the left of the midpoint  head
        prev.next = null;
        TreeNode left = sortedListToBST(head);
        //  You need to pay attention here , Recursion from the right side down requires that you remove the current value , Point to show Next 
        TreeNode right = sortedListToBST(slow.next);
        //  Current node as the midpoint of the tree 
        TreeNode treeNode = new TreeNode(slow.val);
        treeNode.left = left;
        treeNode.right = right;
        return treeNode;
    }

LeetCode Time consuming ：0ms

• summary

1. Find the double pointer at the midpoint of the linked list （ Three pointers ） Law , Quick start
2. According to the idea of solving problems recursively , When dealing with recursion at this level , Some details need to be considered comprehensively