Podela liste oko zadate vrednosti

Napisati funkciju

Cvor<int>* podeli(Cvor<int>* pocetak, int x);

koja preuređuje listu tako da svi elementi manji od x budu ispred svih ostalih, pri čemu se međusobni redosled elemenata unutar obe grupe ne menja, i vraća novi početak liste. Menjaju se samo pokazivači; jedan prolaz kroz listu, dodatna memorija $O(1)$.

Uputstvo: Grade se dve liste uporedo, svaka sa pokazivačem na svoj poslednji čvor, a na kraju se nadovežu. Paziti šta je sledeci poslednjeg čvora.

Ulaz

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

Izlaz

Ispisati elemente preuređene liste.

Primer

Ulaz

6
1 4 3 2 5 2
3

Izlaz

1 2 2 4 3 5

Postavka

main.cpp

#include <iostream>

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

namespace matf {

    // Stavlja elemente manje od x ispred ostalih, cuvajuci redosled u grupama.
    Cvor<int>* podeli(Cvor<int>* pocetak, int x)
    {
        // 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 x;
    std::cin >> x;

    lista = matf::podeli(lista, x);
    ispisi(lista);

    oslobodi(lista);
    return 0;
}

Rešenje

main.cpp

#include <iostream>

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

namespace matf {

    // Stavlja elemente manje od x ispred ostalih, cuvajuci redosled u grupama.
    Cvor<int>* podeli(Cvor<int>* pocetak, int x)
    {
        // Privremeni cvorovi su pocetci dve liste koje se grade.
        Cvor<int> manji(0, nullptr);
        Cvor<int> ostali(0, nullptr);
        Cvor<int>* kraj_manjih = &manji;
        Cvor<int>* kraj_ostalih = &ostali;

        for (Cvor<int>* p = pocetak; p != nullptr; p = p->sledeci) {
            if (p->podatak < x) {
                kraj_manjih->sledeci = p;
                kraj_manjih = p;
            } else {
                kraj_ostalih->sledeci = p;
                kraj_ostalih = p;
            }
        }

        // Bez ovoga bi poslednji cvor mogao da pokazuje nazad, u prvu grupu.
        kraj_ostalih->sledeci = nullptr;
        kraj_manjih->sledeci = ostali.sledeci;
        return manji.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 x;
    std::cin >> x;

    lista = matf::podeli(lista, x);
    ispisi(lista);

    oslobodi(lista);
    return 0;
}