Da li je lista palindrom

Lista je palindrom ako se isto čita sleva nadesno i zdesna nalevo, na primer 1 2 3 2 1 ili 4 7 7 4. Napisati funkciju

bool je_palindrom(Cvor<int>* pocetak);

Dozvoljena dodatna memorija je $O(1)$: bez pomoćnog niza, bez steka i bez rekurzije. Složenost $O(n)$. Posle poziva lista mora da bude ista kao na ulazu.

Uputstvo: Rešenje se sastavlja od gotovih delova: nalaženje sredine (zadatak 4), obrtanje druge polovine (zadatak 3), poređenje i ponovno obrtanje.

Ulaz

U prvom redu učitava se broj n $(1 \le n \le 10^5)$, a zatim n celih brojeva.

Izlaz

U prvom redu ispisati da ili ne, a u drugom listu.

Primer

Ulaz

5
1 2 3 2 1

Izlaz

da
1 2 3 2 1

Primer

Ulaz

4
4 7 7 5

Izlaz

ne
4 7 7 5

Postavka

main.cpp

#include <iostream>

#include "lista.h"   // zbog strukture Cvor

namespace matf {

    Cvor<int>* obrni(Cvor<int>* pocetak)
    {
        // Ovde ide vasa implementacija
        return pocetak;
    }

    // Proverava da li je lista palindrom. Lista posle poziva ostaje ista.
    bool je_palindrom(Cvor<int>* pocetak)
    {
        // Ovde ide vasa implementacija
        return false;
    }

} // namespace matf

Cvor<int>* ucitaj()
{
    int n;
    std::cin >> n;

    Cvor<int>* pocetak = nullptr;
    Cvor<int>* poslednji = nullptr;
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        Cvor<int>* novi = new Cvor<int>(x, nullptr);
        if (poslednji == nullptr)
            pocetak = novi;
        else
            poslednji->sledeci = novi;
        poslednji = novi;
    }
    return pocetak;
}

void ispisi(Cvor<int>* pocetak)
{
    for (Cvor<int>* p = pocetak; p != nullptr; p = p->sledeci)
        std::cout << p->podatak << " ";
    std::cout << std::endl;
}

void oslobodi(Cvor<int>* pocetak)
{
    while (pocetak != nullptr) {
        Cvor<int>* stari = pocetak;
        pocetak = pocetak->sledeci;
        delete stari;
    }
}

int main()
{
    Cvor<int>* lista = ucitaj();

    std::cout << (matf::je_palindrom(lista) ? "da" : "ne") << std::endl;
    ispisi(lista);

    oslobodi(lista);
    return 0;
}

Rešenje

main.cpp

#include <iostream>

#include "lista.h"   // zbog strukture Cvor

namespace matf {

    Cvor<int>* obrni(Cvor<int>* pocetak)
    {
        Cvor<int>* prethodni = nullptr;
        while (pocetak != nullptr) {
            Cvor<int>* sledeci = pocetak->sledeci;
            pocetak->sledeci = prethodni;
            prethodni = pocetak;
            pocetak = sledeci;
        }
        return prethodni;
    }

    // Proverava da li je lista palindrom. Lista posle poziva ostaje ista.
    bool je_palindrom(Cvor<int>* pocetak)
    {
        // Spori staje na poslednjem cvoru prve polovine.
        Cvor<int>* spori = pocetak;
        Cvor<int>* brzi = pocetak;
        while (brzi->sledeci != nullptr && brzi->sledeci->sledeci != nullptr) {
            spori = spori->sledeci;
            brzi = brzi->sledeci->sledeci;
        }

        Cvor<int>* druga = obrni(spori->sledeci);

        // Druga polovina nije duza od prve, pa je ona uslov za kraj.
        bool jeste = true;
        Cvor<int>* p = pocetak;
        for (Cvor<int>* q = druga; q != nullptr; q = q->sledeci) {
            if (p->podatak != q->podatak) {
                jeste = false;
                break;
            }
            p = p->sledeci;
        }

        spori->sledeci = obrni(druga);
        return jeste;
    }

} // namespace matf

Cvor<int>* ucitaj()
{
    int n;
    std::cin >> n;

    Cvor<int>* pocetak = nullptr;
    Cvor<int>* poslednji = nullptr;
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        Cvor<int>* novi = new Cvor<int>(x, nullptr);
        if (poslednji == nullptr)
            pocetak = novi;
        else
            poslednji->sledeci = novi;
        poslednji = novi;
    }
    return pocetak;
}

void ispisi(Cvor<int>* pocetak)
{
    for (Cvor<int>* p = pocetak; p != nullptr; p = p->sledeci)
        std::cout << p->podatak << " ";
    std::cout << std::endl;
}

void oslobodi(Cvor<int>* pocetak)
{
    while (pocetak != nullptr) {
        Cvor<int>* stari = pocetak;
        pocetak = pocetak->sledeci;
        delete stari;
    }
}

int main()
{
    Cvor<int>* lista = ucitaj();

    std::cout << (matf::je_palindrom(lista) ? "da" : "ne") << std::endl;
    ispisi(lista);

    oslobodi(lista);
    return 0;
}