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

• 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) {
/* Divide list into front and tail list */
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);
}
/* 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) {
/* Extract even and odd list */
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* next;
while(cur){
next=cur->next;
cur->next=pre;

pre=cur;
cur=next;

if(next) next=next->next;
}
}
/* Join even and odd list */