# PBinfo #4166 – FLsiDublu – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Se consideră o listă liniară simplu înlănțuită, alocată dinamic, în care elementele sunt de tipul declarat mai jos:

struct Nod
{
    int info;
    Nod *leg;
};
în care câmpul info memorează un număr natural, iar câmpul leg memorează adresa următorului element al listei.

Cerinţa
Să se scrie o funcție C++ cu următorul prototip:

int FLsiDublu(Nod *head);
care, în lista cu n noduri pentru care primul element are adresa memorată în pointerul head, verifică dacă informațiile reținute în primele n/2 noduri formează un șir identic cu informațiile din ultimele n/2 noduri. În caz afirmativ, funcția va returna valoarea memorată la al n/2-lea nod, iar în caz contrar funcția va returna -1. De exemplu, dacă lista conține inițial informațiile 11,2,4,11,2,4, atunci n = 6 și 11,2,4 = 11,2,4, deci funcția va returna informația din al treilea nod, adică 4. Dacă lista conține: 2,1,4,2,1,5, atunci funcția returnează -1. De asemenea, dacă lista conține: 2,1,5,6,2,1,5, atunci funcția returnează -1.  În toate testele lista conține inițial cel puțin un nod.

Important
Soluţia propusă va conţine definiţia funcţiei cerute. Prezenţa în soluţie a altor instrucţiuni poate duce erori de compilare sau de execuţie care vor avea ca efect depunctarea soluţiei.

## Cod sursă C++

```cpp
int FLsiDublu(Nod *head)
{
    Nod *p, *q, *r;
    int n = 0;
    /// numara cate noduri are lista
    for (p = head; p != NULL; p = p->leg)
        n++;
    if (n % 2 == 1) return -1;
    /// pozitionam pointerul q la nodul n/2+1
    n /= 2;
    for (r = q = head; q != NULL && n > 0; q = q->leg)
    {
        n--;
        r = q;
    }
    /// verificam egalitatea celor doua jumatati
    p = head;
    while (q != NULL)
    {
        if (p->info != q->info) return -1;
        p = p->leg;
        q = q->leg;
    }
    return r->info;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4166)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4166/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4166/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)