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

struct node {
  char key;
  node *next;
};

în care câmpul key memorează un caracter, iar câmpul next memorează adresa următorului element al listei

Cerința

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

bool palindrom(node *l);

care returnează true în caz ca lista al cărei prim element are adresa memorată în l formează un palindrom, iar false în caz contrar.

Un palindrom este un șir care citit de la stânga la dreapta sau de la dreapta la stânga rămâne neschimbat.

Restricții și precizări

numele funcției va fi palindrom
lista va conține cel puțin 2 elemente
2 caractere sunt considerate egale daca au acelaşi cod ASCII

Exemplu

Dacă lista conține valorile (r a d a r) funcția va returna true, iar dacă lista conține (a B b a) sau (l i n u x) funcția va returna false.

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. La ieșirea din subprogram lista nu va fi modificată.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema FListaVerPalindrom :

/*
* Algoritm O(N) timp si O(1) memorie:
* Ideea este sa aflam adresa elementului din mijlocul listei si a vecinilor sai
* Trunchiem lista la mijloc si rasturnam una din cele 2 liste rezultate
* Daca sunt egale inseamna ca lista initiala forma un palindrom
* La final avem grija sa refacem legaturile in lista
*/
void _reverse(node *&l) { // procedura de rasturnare a listei
  node *ptr, *next, *prev;
  prev = NULL;
  ptr = l;
  while (ptr != NULL) {
    next = ptr->next;
    ptr->next = prev;
    prev = ptr;
    ptr = next;
  }
  l = prev;
}

bool _equal(node *a, node *b) { // functie care verifica daca 2 liste sunt egale ca lungime si contin aceleasi valori
  while ((a != NULL) && (b != NULL) && (a->key == b->key)) {
    a = a->next;
    b = b->next;
  }
  return (a == NULL) && (b == NULL);
}

bool palindrom(node *l) {
  node *ptr_fast; // folosit pentru determinarea elementului din mijloc
  node *ptr;      // adresa elementului aflat dupa mijlocul listei
  node *q;        // adresa elementului aflat inaintea mijlocului listei
  node *mid;      // adresa mijlocului listei
  bool ans;

  ptr_fast = l;
  ptr = l;
  q = NULL;

  // ptr_fast itereaza din 2 in 2
  // cand va ajunge la final, ptr, care itereaza din 1 in 1, va fi pe pozitia din mijloc
  // iar q il va precede
  while ((ptr_fast != NULL) && (ptr_fast->next != NULL)) {
    ptr_fast = ptr_fast->next->next;
    q = ptr;
    ptr = ptr->next;
  }
  mid = NULL;
  if (ptr_fast != NULL) {  // in caz ca lungimea listei este impara
    mid = ptr;             // nu ne intereseaza elementul din mijloc
    ptr = ptr->next;
  }
  q->next = NULL;          // trunchiem lista
  _reverse(ptr);           // rasturnam o jumatate
  ans = _equal(l, ptr);    // in ans vom retine daca lista formeaza un palindrom
                           // acest rezultat nu poate fi returnat inca pentru ca am stricat lista
  _reverse(ptr);           // readucem jumatatea rasturnata la forma initiala
  if (mid != NULL) {       // refacem legatura la mijloc
    q->next = mid;
  } else {
    q->next = ptr;
  }
  return ans;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1256 FListaVerPalindrom

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1256 FListaVerPalindrom de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1256 FListaVerPalindrom