Concise java. O(nlogn)


  • 1
    A

    Let slow.next to be the pivot. In this way, it is easy to set slow.next = null to cut the list.

    public static TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return new TreeNode(head.val);
        }
        ListNode slow = head, fast = head.next; // pivot should be slow.next. In this way, it is easy to set slow.next = null
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        TreeNode node = new TreeNode(slow.next.val);    // pivot is slow.next
        ListNode next = slow.next.next;
        slow.next = null; // cut the list.
        node.left = sortedListToBST(head);
        node.right = sortedListToBST(next);
        return node;
    }

  • 0

    That's not O(n).


  • 0
    A

    you are right. Should be O(nlogn), like merge sort. Thank you for pointing out!


  • 0

    Can you explain more about the time complexity?


  • 0
    A

    @wwt_1991 are you familiar how to analyze the time complexity of merge sort or quick sort? This is exactly the same. At each round it will go through all n elements to find the middle element. And totally we do this in o(logn) times or o(logn) levels. So in total o(nlogn)


  • 0

    @allenlipeng47 thank you


Log in to reply
 

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