My simple Java solution


  • 11
    D

    public class Solution {

    public TreeNode sortedListToBST(ListNode head) {
    
        if (head == null) { return null; }
        if (head.next == null) { return new TreeNode(head.val); }
    
        ListNode mid = head;
        ListNode pre_mid = null;
        ListNode fast = head;
    
        while (true) {
            if (fast != null && fast.next != null) {
                fast = fast.next.next;
            } else {
                break;
            }
            pre_mid = mid;
            mid = mid.next;
        }
        if (pre_mid != null)
            pre_mid.next = null;
    
    
        TreeNode root = new TreeNode(mid.val);
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(mid.next);
    
        return root;
    }
    

    }


  • 0
    P

    Is this time complexity O(nlg(n))?


  • 3

    we share the same idea, but in my solution, pre_mid is not needed:

    class Solution {
    public:
        TreeNode* sortedListToBST(ListNode* head) {
            if (head == NULL)
                return NULL;
            if (head->next == NULL)
                return new TreeNode(head->val);
            ListNode *fast = head->next->next, *slow = head;
            while (fast != NULL && fast->next != NULL) {
                slow = slow->next;
                fast = fast->next->next;
            }
            TreeNode* root = new TreeNode(slow->next->val);
            root->right = sortedListToBST(slow->next->next);
            slow->next = NULL;
            root->left = sortedListToBST(head);
            return root;
        }
    };

Log in to reply
 

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