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

  /* Vezane liste - Primjer 8 (rekurzivno).
     Sortirano spajanje (merge) dvije sortirane liste.
     Okretanje (invertiranje) liste.
     Sve funkcije za rad s listama su rekurzivne.
  */

/* ======================================================================== */

    /* Tip za pokazivac na element liste. */

typedef struct _element *lista;

    /* Tip za element liste. */

typedef struct _element {
    int broj;            /* Sadrzaj je broj. */
    lista sljed;         /* Pokazivac na sljedeci element u listi. */
} element;

/* ======================================================================== */

    /* Rekurzivna funkcija za sortirano spajanje (merge)
       dvije sortirane liste. */

    /* Rekurzivno izbacuje manji prvi element iz pripadne liste,
       stavlja ga kao prvi element u spojenoj listi, a zatim na njega
       spaja listu dobivenu spajanjem dvije preostale liste
       (liste sljedbenika izbacenog elementa i one druge).
       Rekurzija = obrada liste sljedbenika izbacenog elementa.
       Mora paziti na praznu listu (nema prvog) - tada nema rekurzije,
       sto odgovara kraju rekurzije. */

lista merge_rek(lista prvi_1, lista prvi_2)
{
        /* Sortirano spaja dvije liste (merge). */

    lista prvi;

        /* Ako je jedna lista prazna, rezultat je ona druga lista.
           Tada nema rekurzije (= prekid). */
    if (prvi_1 == NULL) return prvi_2;
    if (prvi_2 == NULL) return prvi_1;

        /* U nastavku obrade, obje liste sigurno NISU prazne. */

        /* Nadji manjeg, od prvog iz prve liste i prvog iz druge liste.
           Stavi ga kao pocetak (prvi element) u spojenoj listi.
           Skrati pripadnu listu za prvi element (kao da ga izbacimo
           s pocetka njegove liste), ponovi cijeli posao na listi
           sljedbenika izbacenog elementa i onoj drugoj listi (spoji ih).
           Tako spojenu (kracu) listu stavi kao listu sljedbenika novog
           prvog (= spoji na prvog), sto daje cijelu spojenu listu. */

    if (prvi_1->broj <= prvi_2->broj) {
        prvi = prvi_1;
        prvi->sljed = merge_rek(prvi_1->sljed, prvi_2);
    }
    else {
        prvi = prvi_2;
        prvi->sljed = merge_rek(prvi_1, prvi_2->sljed);
    }

        /* Vrati pocetak spojene sortirane liste. */
    return prvi;
}

/* ======================================================================== */

    /* Rekurzivna funkcija za invertiranje (naopako okretanje) liste. */

    /* Rekurzivno okrece prvi element u listi i njegovu listu
       sljedbenika (ako lista sljedbenika nije prazna). Tj. polazni
       prvi element dodaje se na KRAJ invertirane liste sljedbenika.
       Rekurzija = obrada liste sljedbenika prvog elementa u listi.
       Mora paziti na
       - praznu listu (nema zadnjeg) - tada nema rekurzije,
       - jednoclanu listu (prvi = zadnji) - to je kraj rekurzije.
       Prvo okrece listu sljedbenika, a zatim prvog doda na kraj! */

lista okreni_listu_rek(lista prvi)
{
        /* Invertira poredak elemenata u listi. */

    lista p1, p2;

        /* Ako je lista prazna, invertirana lista je isto prazna.
           To se moze dogoditi samo u prvom (vanjskom) pozivu. */
    if (prvi == NULL) return NULL;

        /* U nastavku obrade, lista sigurno NIJE prazna. */

        /* Ako je lista jednoclana (prvi je zadnji), onda je invertirana
           lista jednaka polaznoj, tj. nema posla (lista sljedbenika
           prvog elementa je prazna). Tada nema rekurzije (= prekid).
           U protivnom, skrati listu za jedan (prvi) element i rekurzivno
           ponovi cijeli posao na listi sljedbenika prvog elementa.
           Na kraju, dodaj (bivseg) prvog na kraj dobivene liste. */

    if (prvi->sljed != NULL) {    /* Nije zadnji. */

            /* Lista ima bar dva elementa. Zapamti pokazivace na prvi
               i drugi element (p1 na prvi, p2 na drugi). Prvi ce
               postati zadnji u invertiranoj cijeloj listi, a drugi
               ce postati zadnji u invertiranoj listi sljedbenika. */
        p1 = prvi;
        p2 = prvi->sljed;

            /* Invertiraj listu sljedbenika prvog elementa (rekurzija).
               To vrati novi prvi = pocetak invertirane liste. */
        prvi = okreni_listu_rek(prvi->sljed);

            /* Dodaj bivseg prvog (zapamcen u p1) na kraj invertirane
               liste sljedbenika, iza bivseg drugog (zapamcen u p2). */
        p2->sljed = p1;
            /* Uzemlji novog zadnjeg (bivsi prvi, zapamcen u p1). */
        p1->sljed = NULL;
    }

    return prvi;
}

/* ======================================================================== */

    /* Ispod su funkcije za osnovne operacije s listama. */

/* ======================================================================== */

    /* Funkcija za kreiranje jednog novog elementa sa zadanim sadrzajem
       (broj). Koristi se u rekurzivnoj funkciji kreiraj_straga_rek. */

lista kreiraj_novi(int broj)
{
    lista novi = NULL;
/*
    if ((novi = (lista) malloc(sizeof(element))) == NULL)
*/
    novi = (lista) malloc(sizeof(element));
    if (novi == NULL) {
        printf("Alokacija nije uspjela.\n");
        exit(EXIT_FAILURE);    /* exit(1); */
    }

    novi->broj = broj;
    novi->sljed = NULL;

    return novi;
}

/* ======================================================================== */

    /* Rekurzivna funkcija za kreiranje novog elementa i ubacivanje
       na kraj liste. */

    /* Rekurzivno trazi zadnji element u listi.
       Kad ga nadje, kreira novi element i spaja ga na njega.
       Rekurzija = obrada liste sljedbenika prvog elementa u listi.
       Mora paziti na:
        - praznu listu (nema zadnjeg) - tada nema rekurzije,
        - jednoclanu listu (prvi = zadnji) - to je kraj rekurzije. */

lista kreiraj_straga_rek(lista prvi, int broj)
{
    lista novi = NULL;

        /* Ako je lista prazna, kreiraj novi prvi element i vrati
           pripadnu jednoclanu listu (nema rekurzije). Ovo je jedini
           slucaj kad ulazni prvi i novi (vraceni) prvi nisu isti.
           To se moze dogoditi samo u prvom (vanjskom) pozivu) */
    if (prvi == NULL) {
        novi = kreiraj_novi(broj);
        return novi;
    }

        /* U nastavku obrade, lista sigurno NIJE prazna. */

        /* Ako je lista jednoclana (prvi je zadnji), onda kreiraj novi
           element i spoji ga na prvog. Tada nema rekurzije (= prekid).
           U protivnom, skrati listu za jedan (prvi) element i rekurzivno
           ponovi cijeli posao na listi sljedbenika prvog elementa.
           U oba slucaja, prvi element liste se ne mijenja (= ulazni)
           i njega treba vratiti kao pocetak nove (povecane) liste. */

    if (prvi->sljed == NULL) {    /* = zadnji. */
        novi = kreiraj_novi(broj);
        prvi->sljed = novi;
    }
    else    /* Skrati prvu listu (bez prvog).
               Ne trebamo vrijednost funkcije! */
            /* Lista ima bar dva elementa. Nastavi traziti zadnji,
               rekurzivnom obradom liste sljedbenika prvog elementa
               u listi. Ovdje NE trebamo povratnu vrijednost funkcije
               = pocetak nove (povecane) liste sljedbenika. */
        kreiraj_straga_rek(prvi->sljed, broj);

    return prvi;
}

/* ======================================================================== */

    /* Rekurzivna funkcija za brisanje cijele liste. */

    /* Rekurzivno brise prvi element u listi.
       Rekurzija = obrada liste sljedbenika prvog elementa u listi.
       Mora paziti na praznu listu (nema prvog) - tada nema rekurzije,
       sto odgovara kraju rekurzije.
       Prvo brise listu sljedbenika, a zatim prvog! */

lista obrisi_listu_rek(lista prvi)
{
    if (prvi != NULL) {
        obrisi_listu_rek(prvi->sljed);
/*
      Ovdje NE trebamo povratnu vrijednost funkcije!
      Mozemo napisati i
        prvi->sljed = obrisi_listu_rek(prvi->sljed);
*/
        free(prvi);
    }

    return NULL;
}

/* ======================================================================== */

    /* Rekurzivna funkcija za broj elemenata u listi. */

    /* Rekurzivno pribraja prvi element u listi.
       Rekurzija = obrada liste sljedbenika prvog elementa u listi.
       Mora paziti na praznu listu (nema prvog) - tada nema rekurzije,
       sto odgovara kraju rekurzije. */

int broj_elemenata_rek(lista prvi)
{
    if (prvi == NULL)
        return 0;
    else
        return 1 + broj_elemenata_rek(prvi->sljed);
}

/* ======================================================================== */

    /* Rekurzivna funkcija za (skraceni) ispis svih elemenata u listi. */

    /* Rekurzivno ispisuje sadrzaj prvog elementa u listi.
       Rekurzija = obrada liste sljedbenika prvog elementa u listi.
       Mora paziti na praznu listu (nema prvog) - tada nema rekurzije,
       sto odgovara kraju rekurzije.
       Prvo ispisuje sadrzaj prvog, a onda obradjuje listu sljedbenika. */

void ispisi_listu_rek(lista prvi)
{
    if (prvi == NULL)
        printf(" NULL\n");
    else {
        printf(" %d ->", prvi->broj);
        ispisi_listu_rek(prvi->sljed);
    }

    return;
}

/* ======================================================================== */

int main(void)
{
    lista prvi_1 = NULL;    /* Prazna lista! */
    lista prvi_2 = NULL;    /* Prazna lista! */
    lista prvi;
    int broj;

        /* Punjenje prve liste straga. */

        /* Citanje niza brojeva za listu, do broj = 0.
           To je oznaka kraj niza, ali nije clan niza. */
        /* Poredak brojeva u listi je isti kao redoslijed
           citanja, jer dodajemo na kraj liste. */

    printf("Upisite niz cijelih brojeva (0 = kraj).\n");
    do {
        printf("Sljedeci broj:\n");
        scanf("%d", &broj);
        if (broj != 0)
            prvi_1 = kreiraj_straga_rek(prvi_1, broj);
    } while (broj != 0);

        /* Punjenje druge liste straga. */

        /* Citanje niza brojeva za listu, do broj = 0.
           To je oznaka kraj niza, ali nije clan niza. */
        /* Poredak brojeva u listi je isti kao redoslijed
           citanja, jer dodajemo na kraj liste. */

    printf("\n");
    printf("Upisite niz cijelih brojeva (0 = kraj).\n");
    do {
        printf("Sljedeci broj:\n");
        scanf("%d", &broj);
        if (broj != 0)
            prvi_2 = kreiraj_straga_rek(prvi_2, broj);
    } while (broj != 0);

        /* Prva lista:
           ispis broja elemenata i cijele liste. */

    printf("\n Prva lista:\n");
    printf(" Broj elemenata u listi = %d\n",
           broj_elemenata_rek(prvi_1));
    ispisi_listu_rek(prvi_1);

        /* Druga lista:
           ispis broja elemenata i cijele liste. */

    printf("\n Druga lista:\n");
    printf(" Broj elemenata u listi = %d\n",
           broj_elemenata_rek(prvi_2));
    ispisi_listu_rek(prvi_2);


        /* Sortirani spoj (merge) dvije liste. */

    prvi = merge_rek(prvi_1, prvi_2);

        /* Spojena lista:
           ispis broja elemenata i cijele liste. */

    printf("\n Spojena lista:\n");
    printf(" Broj elemenata u listi = %d\n",
           broj_elemenata_rek(prvi));
    ispisi_listu_rek(prvi);


        /* Invertiranje liste. */

    prvi = okreni_listu_rek(prvi);

        /* Invertirana lista:
           ispis broja elemenata i cijele liste. */

    printf("\n Invertirana lista:\n");
    printf(" Broj elemenata u listi = %d\n",
           broj_elemenata_rek(prvi));
    ispisi_listu_rek(prvi);

        /* Obrisi cijelu listu. */

    prvi = obrisi_listu_rek(prvi);

    return 0;
}