#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

struct List
{
int value;
struct List *next;
};

void Put(int num, List **first)
{
List *q=new List;
q->value=num;
q->next=*first;
*first=q;
}

void Print_List(List *first)
{
List *p=first;
while(p!=NULL)
{
printf("\t%d", p->value);
p=p->next;
}
}

List *Sort(List *f1)
{
List *current, *pnt, *p, *f2;
int tmp;
for (current=f1; current->next!=NULL; current=current->next)
 {
  pnt=current;
  for( p=current->next; p!=NULL; p=p->next)
     if ( p->value > pnt->value )
     {
     tmp=pnt->value;
     pnt->value = p->value;
     p->value=tmp;
     }
 }
 Print_List(f1);
 printf("\n");

 f2=f1;
 pnt=f2;
 f1=f1->next;
 f2->next=NULL;
 current=f1;
 p=f1;

 while(f1!=NULL)
 {
 f2=f1;
 current=current->next;
 f1=(f1)->next;
 f2->next=pnt;
 pnt=p;
 p=current;
 }
 delete f1;
 delete current;
 delete pnt;
 delete p;
 return f2;
}

void main()
{
clrscr();
randomize();
int number, amount, i, j;
List **first1=NULL, *first2=NULL;

puts("Sorting of turn.");
printf("Enter amount of numbers: ");
scanf("%d", &amount);

for(i=0; i<amount; i++)
{
number=rand()%100-rand()%100;
Put(number, first1);
}
Print_List(*first1);
printf("\n");


first2=Sort(*first1);
Print_List(first2);
getch();
}