@@ -0,0 +1,2326 @@
+package fundamentals.tree.construct.lc109_convertsortedlisttobinarysearchtree;%0A%0Aimport fundamentals.list.ListNode;%0Aimport fundamentals.tree.TreeNode;%0A%0A/**%0A * Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.%0A */%0Apublic class Solution %7B%0A%0A    public TreeNode sortedListToBST(ListNode head) %7B%0A        if (head == null) %7B%0A            return null;%0A        %7D%0A%0A        // 1.Find middle node: head != null (list has at least 1 node)%0A        ListNode prev = null, mid = head, fast = head;%0A        while (fast.next != null && fast.next.next != null) %7B%0A            prev = (prev == null) ? head : prev.next;%0A            mid = mid.next;%0A            fast = fast.next.next;%0A        %7D%0A%0A        // 2.Split list into two parts: prev=null,mid=head or prev,mid is approriate%0A        ListNode list1 = (prev == null) ? null : head;%0A        ListNode list2 = mid.next;%0A        if (prev != null) %7B%0A            prev.next = null;%0A        %7D%0A        mid.next = null;%0A%0A        // 3.Construct recursively: mid is not null, but list1 and list2 could be%0A        TreeNode root = new TreeNode(mid.val);%0A        root.left = sortedListToBST(list1);%0A        root.right = sortedListToBST(list2);%0A        return root;%0A    %7D%0A%0A    // Correct but different from judge. eg.%5B1,2%5D -%3E me %5B2,1%5D, judge %5B1,null,2%5D%0A    public TreeNode sortedListToBST2(ListNode head) %7B%0A        if (head == null) %7B%0A            return null;%0A        %7D%0A%0A        // 1.Find middle node: head != null (list has at least 1 node)%0A        ListNode slow = head, fast = head;%0A        while (fast.next != null && fast.next.next != null) %7B%0A            slow = (slow == fast) ? slow : slow.next; // wait one step, so slow.next is middle when terminating%0A            fast = fast.next.next;%0A        %7D%0A%0A        // 2.Split list into two parts: slow is head (1 or 2 nodes) or slow.next = middle node%0A        ListNode mid = (slow.next == null) ? slow : slow.next;%0A        ListNode list1 = (head == mid) ? null : head;%0A        ListNode list2 = mid.next;%0A        slow.next = null;%0A        mid.next = null;%0A%0A        // 3.Construct recursively: mid is not null, but list1 and list2 could be%0A        TreeNode root = new TreeNode(mid.val);%0A        root.left = sortedListToBST2(list1);%0A        root.right = sortedListToBST2(list2);%0A        return root;%0A    %7D%0A%0A%7D%0A

leetcode-109 convert sorted list to binary search tree