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.