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

  /* Vezane liste - Primjer 7 (rekurzivno).
     Spajanje (konkatenacija) dvije 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 spajanje (konkatenaciju) dvije liste. */

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

lista spoji_dvije_rek(lista prvi_1, lista prvi_2)
{
        /* Ako je prva lista prazna, rezultat je druga lista.
           To se moze dogoditi samo u prvom (vanjskom) pozivu. */
    if (prvi_1 == NULL) return prvi_2;

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

        /* Ako je prva lista jednoclana (prvi_1 je zadnji),
           onda spoji drugu listu na njega i nema rekurzije (= prekid).
           U protivnom, skrati prvu listu za jedan (prvi) element
           i rekurzivno ponovi cijeli posao na listi sljedbenika
           prvog elementa u prvoj listi (druga lista ostaje ista).
           U oba slucaja, prvi element prve liste se ne mijenja (= ulazni)
           i njega treba vratiti kao pocetak spojene liste. */

    if (prvi_1->sljed == NULL)    /* = zadnji_1. */
        prvi_1->sljed = prvi_2;
    else    /* Skrati prvu listu (bez prvog).
               Ne trebamo vrijednost funkcije! */
            /* Prva lista ima bar dva elementa. Nastavi traziti zadnji,
               rekurzivnom obradom liste sljedbenika prvog elementa
               u prvoj listi. Ovdje NE trebamo povratnu vrijednost
               funkcije = pocetak skracene liste. */
        spoji_dvije_rek(prvi_1->sljed, prvi_2);

        /* Vrati pocetak spojene liste = pocetak prve (jer nije prazna). */
    return prvi_1;
}

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

    /* 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);


        /* Konkatenacija dvije liste. */

    prvi = spoji_dvije_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);

        /* Obrisi cijelu listu. */

    prvi = obrisi_listu_rek(prvi);

    return 0;
}