Obrtanje dela liste

Napisati funkciju

Cvor<int>* obrni_deo(Cvor<int>* pocetak, int l, int r);

koja obrće deo liste od l-tog do r-tog čvora (čvorovi se broje od 1), ostatak liste ostavlja kakav jeste i vraća novi početak liste. Menjaju se samo pokazivači, u jednom prolazu kroz listu. Složenost $O(n)$, dodatna memorija $O(1)$.

Pitanje za razmišljanje: Šta je ovde poseban slučaj kada je l = 1, i kako ga uklanja privremeni čvor ispred liste?

Ulaz

U prvom redu učitava se broj n $(1 \le n \le 10^5)$, a zatim n celih brojeva. Nakon toga učitavaju se brojevi l i r $(1 \le l \le r \le n)$.

Izlaz

Ispisati elemente liste.

Primer

Ulaz

7
1 2 3 4 5 6 7
2 5

Izlaz

1 5 4 3 2 6 7

Postavka

main.cpp

#include <iostream>

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

namespace matf {

    // Obrce deo liste od l-tog do r-tog cvora, brojeci od 1, i vraca pocetak.
    Cvor<int>* obrni_deo(Cvor<int>* pocetak, int l, int r)
    {
        // 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();

    int l, r;
    std::cin >> l >> r;

    lista = matf::obrni_deo(lista, l, r);
    ispisi(lista);

    oslobodi(lista);
    return 0;
}

Rešenje

main.cpp

#include <iostream>

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

namespace matf {

    // Obrce deo liste od l-tog do r-tog cvora, brojeci od 1, i vraca pocetak.
    Cvor<int>* obrni_deo(Cvor<int>* pocetak, int l, int r)
    {
        Cvor<int> privremeni(0, pocetak);

        // Cvor ispred dela koji se obrce; on je uvek stvaran cvor.
        Cvor<int>* ispred = &privremeni;
        for (int i = 1; i < l; ++i)
            ispred = ispred->sledeci;

        // Prvi cvor dela postaje poslednji. Svaki sledeci cvor vadimo iza
        // njega i umecemo odmah iza cvora ispred.
        Cvor<int>* prvi = ispred->sledeci;
        for (int i = l; i < r; ++i) {
            Cvor<int>* naredni = prvi->sledeci;
            prvi->sledeci = naredni->sledeci;
            naredni->sledeci = ispred->sledeci;
            ispred->sledeci = naredni;
        }

        return privremeni.sledeci;
    }

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

    int l, r;
    std::cin >> l >> r;

    lista = matf::obrni_deo(lista, l, r);
    ispisi(lista);

    oslobodi(lista);
    return 0;
}