#include <iostream>
using namespace std;

struct node{
int data;
node *next;
node(int i) : data(i),next(0){}
};

void insert(node *&head,int i){
if (!head)
head = new node(i);
else{
node *new_node = new node(i);
new_node->next = head;
head = new_node;
}
}

void reverse(node *&head){
node *new_head = 0;
while (head){
if (!new_head){
new_head = head;
head = head->next;
new_head->next = 0;
}
else{
node *old = head;
head = head->next;
old->next = new_head;
new_head = old;
}
}
head = new_head;
}

void merge(node *head1,node *head2,node *&head){
node *small = 0;
while (head1 && head2){
if (head1->data < head2->data){
small = head1;
head1 = head1->next;
}
else{
small = head2;
head2 = head2->next;
}
insert(head,small->data);
}
if (head1)
for (;head1;head1 = head1->next)
insert(head,head1->data);
else
for (;head2;head2 = head2->next)
insert(head,head2->data);
reverse(head);
}


int main(){
node *head1 = 0,*head2 = 0,*head = 0;
for (int i = 1;i < 10;++i)
insert(head1,i); //降序
for (int i = 11;i > 0;i -= 2)
insert(head2,i); //升序
reverse(head1); //置逆
merge(head1,head2,head); //合并
for (node *p = head;p;p = p->next) //输出
cout << p->data << " ";
cout << endl;
system("pause");

}