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

typedef struct node node;

struct node {
	int data;
	node * next;
};


void initialize(node **first);
int isEmpty(node *first);
void push(node **first,int key);
void pop(node **first);
node *searchNode(node *first,int key);
void reverse(node **first);
void printNodes(node* first);

node *getTail(node *first);
void tailins(node *r,node **first,node **last);
node *sort(node *r,node **last);


int main()
{
	int key,ch;
	node *head, *tail, *found;
	initialize(&head);
	do {
		printf("0. Wyjscie \n");
		printf("1. Wstaw element  na poczatek listy\n");
		printf("2. Usun element z poczatku listy\n");
		printf("3. Wyszukaj element listy \n");
		printf("4. Odwroc kolejnosc elementow listy\n");
		printf("5. Posortuj elementy listy \n");
		printf("6. Wypisz elementy listy \n");
		scanf("%d",&ch);
		switch(ch) {
			case 0: {
				while(!isEmpty(head)) {
					pop(&head);
				}
				break;
			}
			case 1: {
				printf("Podaj element jaki chcesz wstawic \n");
				scanf("%d",&key);
				push(&head,key);
				break;
			}
			case 2: {
				pop(&head);
				break;
			}
			case 3: {
				printf("Podaj element jaki chcesz wyszukac \n");
				scanf("%d",&key);
				found = searchNode(head,key);
				if(found == NULL)
					printf("Elementu %d nie znaleziono na liscie\n",key);
				else
					printf("Element %d znaleziono na liscie\n",key);
				break;
			}
			case 4: {
				reverse(&head);
				break;
			}
			case 5: {
				tail = getTail(head);
				head = sort(head,&tail);
				break;
			}
			case 6: {
				printNodes(head);
				break;
			}
			default:
				printf("Brak operacji wybierz inny numer");
		}
	} while(ch != 0);
	return 0;
}

void initialize(node **first)
{
	(*first) = NULL;
}

int isEmpty(node *first)
{
	return first == NULL;
}

void push(node **first,int key)
{
	node * x = (node *)malloc(sizeof(node));
	x->data = key;

	x->next = (*first);
	(*first) = x;

}

void pop(node **first)
{
	node *x;
	if((*first) != NULL) {
		x = (*first);
		(*first) = x->next;
		free(x);
	}
}

node *searchNode(node *first,int key)
{
	node *x = first;
	while(x != NULL && x->data != key)
		x = x->next;
	return x;
}

void reverse(node **first)
{
	node *p, *q, *r;

	p = NULL;
	q = (*first);
	while(q != NULL) {
		r = q->next;
		q->next = p;
		p = q;
		q = r;
	}
	(*first) = p;
}

void printNodes(node* first)
{
	node *x = first;
	int counter = 0;
	while(x != NULL) {
		printf("%d -> ",x->data);
		x = x->next;
		counter++;
	}
	printf("NULL\n");
	printf("Liczba elementow listy : %d\n",counter);
}

node *getTail(node *first)
{
	node *x;
	if(first == NULL) {
		x = NULL;
	} else {
		x = first;
		while(x->next != NULL) {
			x = x->next;
		}
	}
	return x;
}

void tailins(node *r,node **first,node **last)
{
	if((*first) == NULL)
		(*first) = r;
	else
		(*last)->next = r;
	(*last) = r;
}

node *sort(node *r,node **last)
{
	node *result;
	node *lowf,*lowl,*midf,*midl,*highf,*highl;
	if(r == NULL) {
		(*last) = NULL;
		result =  r;
	} else {
		lowf = NULL;
		midf = NULL;
		highf = NULL;

		tailins(r,&midf,&midl);
		r = r->next;
		while(r != NULL) {
			if(r->data < midf->data)
				tailins(r,&lowf,&lowl);
			else if(r->data == midf->data)
				tailins(r,&midf,&midl);
			else
				tailins(r,&highf,&highl);
			r = r->next;
		}
		if(lowf != NULL) {
			lowl->next = NULL;
			result = sort(lowf,last);
			(*last)->next = midf;
		} else
			result = midf;
		if(highf != NULL)
			highl->next = NULL;
		midl->next = sort(highf,last);
		if((*last)==NULL)
			(*last) = midl;
	}
	return result;
}