#include <iostream>

using namespace std;

struct cvorListe {
    int vrijednost;
    cvorListe* sljedeci;
}; // zadavanje cvora liste

int main() {
    cvorListe
        *glava = new cvorListe, // kreiranje glave liste
        *zadnji = glava; // pratimo si zadnji element liste

    glava->sljedeci = NULL; // glava nema sljedeceg u pocetku

    for(int i=0;i<10;i++) { // pomocu petlje unijet cemo 10 brojeva u listu
        int unos;
        cin>>unos;
        cvorListe* el = new cvorListe; // novi element liste
        el->vrijednost = unos; // postavimo mu vrijednost
        el->sljedeci = NULL; // novi element jos zasad nema sljedeceg
        zadnji->sljedeci = el; // u ovom slucaju, "zadnji" je zapravo prosli element, bio je zadnji prije nego smo dodali novi
                               // zapravo predzadnji element spojimo sa zadnjim
        zadnji = el; // sad će novi element biti zadnji
    }

    // ispis svih elemenata vezane liste

    cvorListe* el = glava->sljedeci; // varijabla el pratit ce nam trenutni element, ne krecemo od glave jer ona ne drzi vrijednost, nego tek od sljedeceg

    while(el!=NULL) { // petlja se izvrsava sve dok ne dodemo do zadnjeg
        cout << el->vrijednost << endl;
        el=el->sljedeci; // petlja se prebacuje na sljedeci element
    }

    // tipican bubble sort na vezanoj listi

    bool zamjena;

    cvorListe *lPtr; // lijevi pointer pokazuje na pocetak liste
    cvorListe *rPrt = NULL; // desni pointer pokazivat ce na kraj liste nakon prvog prolaza
    do
    {
        zamjena = 0;
        lPtr = glava;
        while(lPtr->sljedeci != rPrt)
        {
            if (lPtr->vrijednost > lPtr->sljedeci->vrijednost)
            {
                // zamjeniti lPtr i lPtr->sljedeci (isto kao da zamjenimo vrijednost[j] i vrijednost[j+1] u poljima)
                int temp = lPtr->vrijednost;
                lPtr->vrijednost = lPtr->sljedeci->vrijednost;
                lPtr->sljedeci->vrijednost = temp;
                zamjena = 1;
            }
            lPtr = lPtr->sljedeci;
        }
        rPrt = lPtr;

    }
    while(zamjena);


    cout << endl << endl;
    // opet ispis, ovaj put sortirano
    el = glava->sljedeci; // varijabla el pratit ce nam trenutni element, ne krecemo od glave jer ona ne drzi vrijednost, nego tek od sljedeceg

    while(el!=NULL) { // petlja se izvrsava sve dok ne dodemo do zadnjeg
        cout << el->vrijednost << endl;
        el=el->sljedeci; // petlja se prebacuje na sljedeci element
    }
    return 0;
}