#include <stdio.h>
#include <stdlib.h>
typedef struct lista
{
    int dana;
    struct lista* nastepny;
    struct lista* poprzedni;
} lista;
lista* head;
lista* DodajWezel(int x)
{
    lista* nowy=(lista*)malloc(sizeof(lista));
    nowy->dana=x;
    nowy->nastepny=NULL;
    nowy->poprzedni=NULL;
    return nowy;
}
void DodajElementNaPoczatku(int x)
{
    lista* element=DodajWezel(x);
    if(head==NULL)
    {
        head=element;
        return;
    }
    head->poprzedni=element;
    element->nastepny=head;
    head=element;
}
void DodajElementNaKoncu(int x)
{
    lista* element=DodajWezel(x);
    lista* temp= head;
    if(head==NULL)
    {
        head=element;
        return;
    }
    while(temp->nastepny!=NULL)
    {
        temp=temp->nastepny;
    }
    temp->nastepny=element;
    element->poprzedni=temp;
}
void WyswietlListe()
{
    lista*temp=head;
    if(head==NULL)
    {
        printf("Lista pusta\n");
        exit(1);
    }
    printf("\nPoczatek listy\n");
    while(temp!=NULL)
    {
        printf("%d \n", temp->dana);
        temp=temp->nastepny;
    }
    printf("\nKoniec listy\n");
}
int DlugoscListy()
{
    lista*temp=head;
    if(head==NULL)
    {
        printf("Lista pusta\n");
        exit(1);
    }
    int i=0;
    while(temp!=NULL)
    {
        temp=temp->nastepny;
        i++;
    }
    return i;
}
lista** ListaNaTablice(int dlugosc)
{
    lista* temp=head;
    lista** tab;
    tab=(lista**)malloc(dlugosc*sizeof(lista*));
    if(tab==NULL)
    {
        printf("Blad malloca \n");
        exit(1);
    }
    int i=0;
    while(temp!=NULL)
    {
        tab[i]=temp;
        temp=temp->nastepny;
        i++;
    }
    return tab;
}

int porownaj(const void* first, const void* second)
{
    lista* a = *(lista**)first;
    lista* b = *(lista**)second;
    if((a->dana)>(b->dana)) return 1;
    if((a->dana)==(b->dana)) return 0;
    else return -1;
}
void Sortowanie(lista** tab, int dlugosc)
{
    qsort(tab, dlugosc, sizeof(tab), porownaj);
}
void TablicaNaListe(lista** tab, int dlugosc)
{
    lista* obecny;
    lista* kolejny;
    head=tab[0];
    obecny=head;
    int i=1;
    for(i=1;i<dlugosc;i++)
    {
        kolejny=tab[i];
        obecny->nastepny=kolejny;
        kolejny->poprzedni=obecny;
        obecny=kolejny;
    }
    obecny->nastepny=NULL;
}
int main(void)
{
    head=NULL;
    lista** tab;
    int k=0;
    int x=0;
    printf("Podaj ilosc elementow do wprowadzenia: ");
    scanf("%d", &k);
    int i=0;
    for(i=0;i<k;i++)
    {
        printf("Podaj element: ");
        scanf("%d", &x);
        DodajElementNaPoczatku(x);
    }
    int d=DlugoscListy();
    printf("Lista ma %d elementow\n", d);
    printf("Lista przed sortowaniem: \n");
    WyswietlListe();
    ListaNaTablice(d);
    tab=ListaNaTablice(d);
    Sortowanie(tab, d);
    TablicaNaListe(tab, d);
    printf("Lista po sortowaniu: \n");
    WyswietlListe();
    free(tab);
    return 0;
}