Sredina liste i $k$-ti element od kraja

Napisati funkcije

Cvor<int>* sredina(Cvor<int>* pocetak);
Cvor<int>* kti_od_kraja(Cvor<int>* pocetak, int k);
void obrisi_kti_od_kraja(Cvor<int>*& pocetak, int k);

Funkcija sredina vraća srednji čvor liste; ako lista ima paran broj elemenata, vraća drugi od dva srednja. Funkcija kti_od_kraja vraća k-ti čvor od kraja (poslednji čvor je prvi od kraja), a funkcija obrisi_kti_od_kraja taj čvor briše.

Dužina liste se ne sme koristiti. Sve tri funkcije rade u jednom prolazu kroz listu, sa $O(1)$ dodatne memorije.

Pitanja za razmišljanje: Zašto brzi pokazivač staje baš kada spori stigne do sredine? Koliko čvorova treba da bude rastojanje između dva pokazivača da bi se našao prethodnik k-tog čvora od kraja? Šta se dešava kada je k jednako dužini liste, i kako privremeni čvor ispred liste uklanja taj poseban slučaj?

Ulaz

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

Izlaz

U prvom redu ispisati srednji element liste, u drugom k-ti element od kraja, a u trećem listu iz koje je k-ti element od kraja obrisan.

Primer

Ulaz

5
1 2 3 4 5
2

Izlaz

3
4
1 2 3 5

Primer

Ulaz

4
10 20 30 40
4

Izlaz

30
10
20 30 40

Postavka

main.cpp

#include <iostream>

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

namespace matf {

    // Vraca srednji cvor liste, a ako ih ima dva, drugi od njih.
    Cvor<int>* sredina(Cvor<int>* pocetak)
    {
        // Ovde ide vasa implementacija
        return pocetak;
    }

    // Vraca k-ti cvor od kraja liste (poslednji cvor je prvi od kraja).
    Cvor<int>* kti_od_kraja(Cvor<int>* pocetak, int k)
    {
        // Ovde ide vasa implementacija
        return pocetak;
    }

    // Brise k-ti cvor od kraja liste.
    void obrisi_kti_od_kraja(Cvor<int>*& pocetak, int k)
    {
        // Ovde ide vasa implementacija
    }

} // 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 k;
    std::cin >> k;

    std::cout << matf::sredina(lista)->podatak << std::endl;
    std::cout << matf::kti_od_kraja(lista, k)->podatak << std::endl;

    matf::obrisi_kti_od_kraja(lista, k);
    ispisi(lista);

    oslobodi(lista);
    return 0;
}

Rešenje

main.cpp

#include <iostream>

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

namespace matf {

    // Vraca srednji cvor liste, a ako ih ima dva, drugi od njih.
    Cvor<int>* sredina(Cvor<int>* pocetak)
    {
        Cvor<int>* spori = pocetak;
        Cvor<int>* brzi = pocetak;

        while (brzi != nullptr && brzi->sledeci != nullptr) {
            spori = spori->sledeci;
            brzi = brzi->sledeci->sledeci;
        }

        return spori;
    }

    // Vraca k-ti cvor od kraja liste (poslednji cvor je prvi od kraja).
    Cvor<int>* kti_od_kraja(Cvor<int>* pocetak, int k)
    {
        // Prednji pokazivac je k cvorova ispred zadnjeg, pa kada on izadje
        // iz liste, zadnji stoji na k-tom cvoru od kraja.
        Cvor<int>* prednji = pocetak;
        for (int i = 0; i < k; ++i)
            prednji = prednji->sledeci;

        Cvor<int>* zadnji = pocetak;
        while (prednji != nullptr) {
            prednji = prednji->sledeci;
            zadnji = zadnji->sledeci;
        }

        return zadnji;
    }

    // Brise k-ti cvor od kraja liste.
    void obrisi_kti_od_kraja(Cvor<int>*& pocetak, int k)
    {
        // Privremeni cvor ispred liste daje prethodnika i prvom cvoru, pa
        // brisanje prvog cvora nije poseban slucaj. Rastojanje je k + 1, jer
        // nam treba prethodnik cvora koji se brise.
        Cvor<int> privremeni(0, pocetak);

        Cvor<int>* prednji = &privremeni;
        for (int i = 0; i <= k; ++i)
            prednji = prednji->sledeci;

        Cvor<int>* zadnji = &privremeni;
        while (prednji != nullptr) {
            prednji = prednji->sledeci;
            zadnji = zadnji->sledeci;
        }

        Cvor<int>* stari = zadnji->sledeci;
        zadnji->sledeci = stari->sledeci;
        delete stari;

        pocetak = 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 k;
    std::cin >> k;

    std::cout << matf::sredina(lista)->podatak << std::endl;
    std::cout << matf::kti_od_kraja(lista, k)->podatak << std::endl;

    matf::obrisi_kti_od_kraja(lista, k);
    ispisi(lista);

    oslobodi(lista);
    return 0;
}