Obrtanje liste

Napisati funkciju

Cvor<int>* obrni(Cvor<int>* pocetak);

koja obrće jednostruko povezanu listu i vraća njen novi početak. Funkcija ne sme da pravi nove čvorove niti da prepisuje podatke iz čvora u čvor: menjaju se samo pokazivači sledeci. Složenost $O(n)$, dodatna memorija $O(1)$.

Pitanja za razmišljanje: Koja su tri pokazivača potrebna u petlji i zašto je redosled dodela bitan? Šta se dešava sa rekurzivnom verzijom na najvećem ulazu? Kako bi ista funkcija izgledala kao članica klase Lista?

Ulaz

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

Izlaz

Ispisati elemente obrnute liste.

Primer

Ulaz

4
1 2 3 4

Izlaz

4 3 2 1

Postavka

main.cpp

#include <iostream>

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

namespace matf {

    // Obrce listu menjanjem pokazivaca i vraca njen novi pocetak.
    Cvor<int>* obrni(Cvor<int>* pocetak)
    {
        // Ovde ide vasa implementacija
        return pocetak;
    }

} // 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();

    lista = matf::obrni(lista);
    ispisi(lista);

    oslobodi(lista);
    return 0;
}

Rešenje

main.cpp

#include <iostream>

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

namespace matf {

    // Obrce listu menjanjem pokazivaca i vraca njen novi pocetak.
    Cvor<int>* obrni(Cvor<int>* pocetak)
    {
        Cvor<int>* prethodni = nullptr;
        Cvor<int>* tekuci = pocetak;

        while (tekuci != nullptr) {
            // Sledbenika pamtimo pre nego sto pregazimo jedinu vezu do njega.
            Cvor<int>* sledeci = tekuci->sledeci;
            tekuci->sledeci = prethodni;
            prethodni = tekuci;
            tekuci = sledeci;
        }

        return prethodni;
    }

} // 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();

    lista = matf::obrni(lista);
    ispisi(lista);

    oslobodi(lista);
    return 0;
}