My 15 lines of C++ code

  • 0

    Using fast-slow pointers to track the middle point of the linked list.
    Using another prev pointer to track the previous position of slow pointer so that the first half linked list's end position can be set to NULL.

    class Solution {
        TreeNode* dfs(ListNode* node) {
            if(node == NULL) return NULL;
            if(node->next == NULL) return new TreeNode(node->val);
            ListNode *fast = node;
            ListNode *slow = node;
            ListNode *prev = NULL;
            while(fast!=NULL && fast->next != NULL) {
                fast = fast->next->next;
                prev = slow;
                slow = slow->next;
            prev->next = NULL;
            TreeNode *curr = new TreeNode(slow->val);
            curr->left = dfs(node);
            curr->right = dfs(slow->next);
            return curr;
        TreeNode* sortedListToBST(ListNode* head) {
            return dfs(head);

Log in to reply

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