# include < iostream >
# include < fstream >
using namespace std ;
struct Node {
int val;
Node * prev ;
Node * next ;
};
void split_list ( Node * head , Node ** even_head , Node ** odd_head ) {
Node * even_tail = NULL ;
Node * odd_tail = NULL ;
Node * curr = head ;
int i = 1 ;
while ( curr != NULL ) {
Node * new_node = new Node { curr ->val, NULL , NULL };
if (i % 2 == 0 ) {
// add to even list
if (* even_head == NULL ) {
* even_head = new_node ;
} else {
even_tail -> next = new_node ;
new_node -> prev = even_tail ;
}
even_tail = new_node ;
} else {
// add to odd list
if (* odd_head == NULL ) {
* odd_head = new_node ;
} else {
odd_tail -> next = new_node ;
new_node -> prev = odd_tail ;
}
odd_tail = new_node ;
}
curr = curr -> next ;
i++;
}
}
void print_list ( Node * head ) {
Node * curr = head ;
while ( curr != NULL ) {
cout << curr ->val << " " ;
curr = curr -> next ;
}
cout << endl ;
}
int main () {
ifstream fin ( "input.txt" ) ;
// create the linked list
Node * head = NULL ;
Node * tail = NULL ;
int num;
while (fin >> num) {
Node * new_node = new Node {num, tail , NULL };
if ( tail == NULL ) {
head = new_node ;
} else {
tail -> next = new_node ;
}
tail = new_node ;
}
fin. close ();
cout << "Original list : " ;
print_list ( head );
// split list into even and odd lists
Node * even_head = NULL ;
Node * odd_head = NULL ;
split_list ( head , & even_head , & odd_head );
cout << " Even list : " ;
print_list ( even_head );
cout << " Odd list : " ;
print_list ( odd_head );
// free memory
Node * curr = head ;
while ( curr != NULL ) {
Node * next = curr -> next ;
delete curr ;
curr = next ;
}
curr = even_head ;
while ( curr != NULL ) {
Node * next = curr -> next ;
delete curr ;
curr = next ;
}
curr = odd_head ;
while ( curr != NULL ) {
Node * next = curr -> next ;
delete curr ;
curr = next ;
}
return 0 ;
}