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

struct nodoLista {
    int valore;
    struct nodoLista *nextPtr;
};

typedef struct nodoLista Lista;

// Prototipi
void suf_insert(Lista **ptrPtr, int val);
void print_list(Lista *ptr);
void dividi_lista(Lista *src, Lista **destPari, Lista **destDispari);

int main() {
    Lista *lista_mista = NULL;
    Lista *lista_pari = NULL;
    Lista *lista_dispari = NULL;
    
    // Popoliamo la lista di partenza
    suf_insert(&lista_mista, 12);
    suf_insert(&lista_mista, 7);
    suf_insert(&lista_mista, 4);
    suf_insert(&lista_mista, 9);
    suf_insert(&lista_mista, 22);
    suf_insert(&lista_mista, 15);
    
    printf("Lista Originale: ");
    print_list(lista_mista); // Atteso: 12 7 4 9 22 15
    
    // Chiamata alla tua funzione
    dividi_lista(lista_mista, &lista_pari, &lista_dispari);
    
    printf("Lista PARI:      ");
    print_list(lista_pari);    // Atteso: 12 4 22
    
    printf("Lista DISPARI:   ");
    print_list(lista_dispari); // Atteso: 7 9 15
    
    return 0;
}

// Funzione fornita dal professore (da usare!)
void suf_insert(Lista **ptrPtr, int val) {
    while(*ptrPtr!=NULL)
        ptrPtr = &((*ptrPtr)->nextPtr);

    Lista *tmp = (Lista *)malloc(sizeof(Lista));
    tmp->valore = val;
    tmp->nextPtr = *ptrPtr;
    *ptrPtr = tmp;
    
}

void print_list(Lista *ptr) {
    while(ptr != NULL) {
        printf("%d ", ptr->valore);
        ptr = ptr->nextPtr;
    }
    printf("\n");
}

/* ========================================================================= */
/* ESERCIZIO DELLO STUDENTE                                                  */
/* ========================================================================= */

/* PRE:  'src' punta alla testa di una lista valida (può essere NULL).
 * 'destPari' e 'destDispari' sono doppi puntatori validi a liste inizializzate a NULL.
 * POST: Le due liste di destinazione vengono popolate con i rispettivi valori,
 * mantenendo l'ordine originale. La lista 'src' rimane inalterata.
 */
void dividi_lista(Lista *src, Lista **destPari, Lista **destDispari) {
    // CASO BASE: Abbiamo finito di leggere la lista mista
    if (src == NULL) {
        return;
    }

    // PASSO 1: Smistiamo il valore corrente usando la funzione sicura!
    if (src->valore % 2 == 0) {
        suf_insert(destPari, src->valore);
    } else {
        suf_insert(destDispari, src->valore);
    }

    // PASSO 2: Chiamata ricorsiva sul prossimo nodo.
    // Nota: passiamo destPari e destDispari così come sono, senza & o *, 
    // perché sono già dei doppi puntatori (Lista **) perfetti per la firma della funzione.
    dividi_lista(src->nextPtr, destPari, destDispari);
}