Lista cu parități alternante

Tipul de date pentru nodurile listei

Fiecare nod are două câmpuri: info, numărul memorat, și urm, adresa nodului următor. Ultimul nod are în câmpul urm adresa nulă, NULL.

struct nod {
    int info;
    nod* urm;
};

Subprogramul adaug

Subprogramul modifică adresele primului și ultimului nod, iar programul apelant trebuie să primească valorile noi. De aceea p și u se transmit prin referință, iar x se transmite prin valoare.

Etapele adăugării sunt următoarele:

1. Se alocă dinamic un nod nou, în câmpul info al căruia se memorează x. Câmpul urm primește valoarea NULL, fiindcă noul nod devine ultimul nod al listei.
2. Dacă lista este vidă, adică p este NULL, noul nod devine primul nod al listei, deci p primește adresa lui.
3. Dacă lista nu este vidă, noul nod se leagă după ultimul nod: câmpul urm al nodului indicat de u primește adresa noului nod.
4. În ambele cazuri, u primește adresa noului nod.

void adaug(nod*& p, nod*& u, int x) {
    nod* nou = new nod;
    nou->info = x;
    nou->urm = NULL;

    if (p == NULL)
        p = nou;
    else
        u->urm = nou;
    u = nou;
}

Adresa ultimului nod este cunoscută, deci adăugarea nu cere parcurgerea listei și se face într-un număr constant de operații, oricâte noduri ar avea lista.

Construirea listei

Numerele impare din intervalul [1,n] sunt 1, 3, 5, …, n − 1, iar cele pare sunt 2, 4, 6, …, n, fiindcă n este par. Fiecare categorie are n/2 elemente. Numerele impare trebuie adăugate în ordine crescătoare, cele pare în ordine descrescătoare, iar paritățile trebuie să alterneze.

Lista se construiește deci în n/2 pași. La pasul i, cu i de la 1 la n/2, se adaugă:

• numărul impar 2i − 1, adică al i-lea număr impar în ordine crescătoare;
• numărul par n − 2i + 2, adică al i-lea număr par în ordine descrescătoare.

Se obține lista 1, n, 3, n − 2, 5, n − 4, …, n − 1, 2, care începe cu un număr impar. Pentru n = 6 lista este 1 6 3 4 5 2, adică prima dintre variantele date în exemplu.