Why my answer exceeds the time limit?


  • 0
    L
    void reorderList(ListNode *head) {
        if((head==NULL)||(head->next==NULL)||(head->next->next==NULL)) return; // If there are at most two nodes, do nothing
        ListNode* pre_end;
        ListNode* end;
        ListNode* head_next;
        pre_end=find_pre_end(head); // pre_node stands for the parent node of the ending node;
        end=pre_end->next;          // end stands for the ending node
        head_next=head->next; 
        if(head_next==pre_end){   // if there are three nodes, switch the second node and third node;
            head->next=end;
            end->next=pre_end;
            pre_end->next=NULL;
            return;
        }
        head->next=end;    
        pre_end->next=NULL;
        reorderList(head_next); 
        end->next=head_next;
    }
    ListNode* find_pre_end(ListNode* head){
        if((head==NULL)||(head->next==NULL)) return head;
        ListNode* pre; ListNode* curr;
        curr=head;
        while(curr->next!=NULL){
            pre=curr;
            curr=curr->next;
        }
        return pre; // find the node just before the ending node
    }

  • 1
    M

    Since this solution is a O(n^2). Best solution for this problem is O(n).


Log in to reply
 

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