Java 1ms solution: O(nlogn) time, O(1) space


  • -1
    Y
    public class Solution {
        public TreeNode sortedListToBST(ListNode head) {
            // 2:40pm - 3:05pm
            if (head == null) {
                return null;
            }
            ListNode mid = head;
            ListNode fast = head;
            ListNode preMid = null;
            while (fast != null && fast.next != null && fast.next.next != null) {
                preMid = mid;
                mid = mid.next;
                fast = fast.next.next;
            }
            TreeNode root = new TreeNode(mid.val);
            if (preMid != null) {
                preMid.next = null;
                root.left = sortedListToBST(head);
            }
            root.right = sortedListToBST(mid.next);
            return root;
        }
    }

  • 0
    C

    Could you explain the mid, fast, and preMid part?


  • 0
    Y

    I make the mid node as root, and construct the left subtree from nodes before the mid node, and the right subtree from the nodes following root. Therefore, the fast and mid are just the same as code that you use to find the mid node.

    For the left subtree, knowing the head is not enough, since I need to cut off the connection from premid to mid, by setting premid.next = null; And that is why I need to know premid.

    since it is a singly linked list!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.