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

#ifndef DEBUG
#define DEBUG(...) printf(__VA_ARGS__)
#endif

#define MAX_SIZE 10
typedef struct Node{
    struct Node *next;
    int val;
} node;

int add_node(node **head, int val) {
    node *new;

    new = (node *)malloc(sizeof(node));
    if (!new) return -1;

    new->val = val;
    new->next = *head;
    *head = new;

    return 0;
}

void print_list(node *head) {
    node *trenutni;

    if(!head) return;

    for(trenutni=head; trenutni!=NULL; trenutni=trenutni->next) printf("%d  ", trenutni->val);
    printf("\n");
}

void bubble_sort(node **head) {
    int counter = 0;
    int n = 10;
    int brojswaps;
    node *trenutni = (*head)->next;
    node *prethodni;
    node *temp;

    while(n > 0){
        temp = *head;
        prethodni = *head;
        trenutni = (*head)->next;
        counter = 0;
        brojswaps = 0;
        //for(trenutni = (*head)->next; trenutni != NULL; trenutni = trenutni->next){
        while(trenutni != NULL){
            //uvjet di moram namjestit head
            //ova 2 if su uvjeti u slucajevima  gdje se desava zamjena
            counter++;
            //printf("t = %d, head = %d, prethod = %d, tmp=%d\n", trenutni->val, (*head)->val, prethodni->val,temp->val);
            if(prethodni->val > trenutni->val && prethodni == *head){
                prethodni->next = trenutni->next;
                trenutni->next = prethodni;
                *head = trenutni;
                //ovisno ako se mjenjo head mjenjo se i temp u tom trenutku
                temp = trenutni;
                trenutni = prethodni->next;
                brojswaps++;
                continue;
            }else if(prethodni->val > trenutni->val && prethodni != *head){
                //printf("nh t = %d, prethodn = %d\n", trenutni->val, prethodni->val);
                prethodni->next = trenutni->next;

                //u slucaju neke zamjene temp->next je trenutni
                //ali i pomakni sad tmp na taj novi
                temp->next = trenutni;
                temp = temp->next;

                trenutni->next = prethodni;
                trenutni = prethodni->next;
                brojswaps++;
                continue;
            }

            //ako nema zamjene
            //printf("nema zam t = %d, prethodn = %d\n", trenutni->val, prethodni->val);
            prethodni = prethodni->next;
            trenutni = trenutni->next;
            if(counter > 1) temp = temp->next;
            //printf("nema zam t = %d, prethodn = %d\n", trenutni->val, prethodni->val);
        }
        //if(brojswaps == 0) break;
        print_list(*head);
        //printf("broj swap = %d\n", brojswaps);
        if(brojswaps == 0) break;
        n--;
    }
}

int main() {
    node *head = NULL;
    int i, val;

    for(i=0; i<MAX_SIZE; i++) {
        scanf("%d", &val);
        add_node(&head, val);
    }

    printf("\nLista prije sortiranja:\n");
    print_list(head);

    printf("\nLista za vrijeme sortiranja:\n");
    bubble_sort(&head);

    printf("\nSortirana lista:\n");
    print_list(head);

    return 0;
}