C++ O(1) space with explanation and an even/odd reorder version (49ms beats 91.7%)


  • 0

    Suppose we have a list [1,2,3,4,5,6,7]
    Steps as follow:

    • Divide the list into front list: [1,2,3,4] and tail list: [5,6,7]
    • Reverse the tail list to [7,6,5]
    • Join front and tail list,
       1      ->2      ->3      ->4
         ->7       ->6      ->5
    
    • Result: [1,7,2,6,3,5,4]
        void reorderList(ListNode* head) {
            if(!head) return;
            ListNode* front=head; 
            /* Divide list into front and tail list */
            ListNode* slow=head;
            ListNode* fast=head->next;
            while(fast){
                slow=slow->next;
                fast=fast->next?fast->next->next:NULL;
            }
            ListNode* tail=slow->next;
            slow->next=NULL;
            /* Reverse tail list */
            ListNode* pre=NULL;
            ListNode* cur=tail;
            ListNode* next;
            while(cur){
                next=cur->next;
                cur->next=pre;
                
                pre=cur;
                cur=next;
                
                if(next) next=next->next;
            }
            tail=pre;
            joinList(front,tail);
            head=front;
        }
        /* Join front list and tail list */
        void joinList(ListNode* front,ListNode* tail){
            if(!tail) return;
            ListNode* frontNext=front->next;
            ListNode* tailNext=tail->next;
            
            while(front&&tail){
                front->next=tail;
                tail->next=frontNext;
                
                front=frontNext;
                tail=tailNext;
                
                if(front) frontNext=front->next;
                if(tail) tailNext=tail->next;
            }
        }
    

    To be honest, I mistook the problem as to reorder list by even/odd at first,
    like that,
    Sample input: [1,2,3,4,5,6,7]
    even list:1,3,5,7,
    odd list: 6,4,2,
    Output: [1,6,3,4,5,2,7]
    Anyway, just share it as well, slightly different from above one.

        void reorderList(ListNode* head) {
            if(!head) return;
            ListNode* evenHead=head;
            ListNode* oddHead=head->next;
            /* Extract even and odd list */
            ListNode* even=evenHead;
            ListNode* odd=oddHead;
            while(even&&odd){
                if(even->next) even->next=even->next->next;
                if(odd->next) odd->next=odd->next->next;
                even=even->next;
                odd=odd->next;
            }
            /* Reverse odd list */
            ListNode* pre=NULL;
            ListNode* cur=oddHead;
            ListNode* next;
            while(cur){
                next=cur->next;
                cur->next=pre;
                
                pre=cur;
                cur=next;
                
                if(next) next=next->next;
            }
            oddHead=pre;
            joinList(evenHead,oddHead);
            head=evenHead;
        }
        /* Join even and odd list */
        void joinList(ListNode* evenHead,ListNode* oddHead){
            if(!oddHead) return;
            ListNode* evenNext=evenHead->next;
            ListNode* oddNext=oddHead->next;
            
            while(evenHead&&oddHead){
                evenHead->next=oddHead;
                oddHead->next=evenNext;
                
                evenHead=evenNext;
                oddHead=oddNext;
                
                if(evenHead) evenNext=evenHead->next;
                if(oddHead) oddNext=oddHead->next;
            }
        }
    

Log in to reply
 

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