#include
using namespace std;
class ListNode
{
public:
int data;
ListNode* next;
ListNode(int val){
this->data = val;
this->next = NULL;
}
};
ListNode* oddEven(ListNode* head){
if(head == NULL) return NULL;
ListNode* oh,*ot,*eh,et;
oh=ot=head;
eh=et = head->next;
ListNode temp = eh->next;
oh->next = eh->next = NULL;
// we will do insertion at the end
while(temp != NULL){
// for odd one
ot->next = temp;
ot = temp;
temp = temp->next;
ot->next = NULL;
if(temp == NULL){break;}
// for even one
et->next = temp;
et = temp;
temp = temp->next;
et->next = NULL;
}
ot->next = eh;
return oh;
}
void insertAtTail(ListNode *&head, int data) {
if(head == NULL) {
head = new ListNode(data);
return;
}
ListNode *tail = head;
while(tail->next != NULL) {
tail = tail->next;
}
tail->next = new ListNode(data);
return;
}
void createList(ListNode* head){
int data;
cin>>data;
while(data!=-1) {
insertAtTail(head, data);
cin>>data;
}
}
int main(){
int n;
cin>>n;
cout<<"Original List: ";
ListNode* head = NULL;
createList(head);
cout<<"Modified List: "<<oddEven(head)<<endl;
return 0;
}