#include <iostream>
#include <stdlib.h>

using namespace std;

struct Node1 {
    int cislo;
    Node1 *dalsi;

    Node1(int i, Node1 * n) {
        cislo = i;
        dalsi = n;
    }
};

struct Node2 {
    int cislo;
    Node2 *dalsi;
    Node2 *back;

    Node2(int i, Node2 *n, Node2 * b) {
        cislo = i;
        dalsi = n;
        back = b;
    }
};





Node1* vytvor1(int *pole, int pocet) {  // Jednosmerny spojovy seznam
    Node1* prvni = NULL;

    for (int i = pocet - 1; i >= 0; i--){
        prvni = new Node1(pole[i], prvni);
      }
    return prvni;
}



Node1* vytvorc(int *pole, int pocet) {   // Cyklicky spojovy seznam
    Node1* prvni = NULL;
    prvni = new Node1(pole[pocet-1], prvni);
       for (int i = pocet-2; i >= 0; i--){
      prvni = new Node1(pole[i], prvni);
    }
    return prvni;
}



Node2* vytvor2(int *pole, int pocet) {     // Dvojsmerny spojovy seznamu
    Node2* prvni = new Node2(pole[0], NULL, NULL);
    Node2* predchozi = prvni;
    Node2* aktualni;

    for (int i = 1; i < pocet; i++) {
        aktualni = new Node2(pole[i], NULL, predchozi);
        predchozi->dalsi = aktualni;
        predchozi = aktualni;
    }
    return prvni;
}



void vypis1(Node1 *zac) {  // Vypis Jednosmerneho spojoveho seznamu
    while(zac){
        cout << zac->cislo << " ";
        zac = zac->dalsi;
    }
}



void vypisc(Node1 *zac) {  // Vypis Cyklickeho spojovy seznam
    Node1 *prvni = zac;
    while (zac){
        cout << zac->cislo << " ";
        zac = zac->dalsi;
    }
    cout << endl;
}



void vypis2(Node2 *zac) {  // Vypis dvojsmerneho spojoveho seznamu
    Node2* prvni = zac;

    while (zac) {
        cout << zac->cislo << " ";
        zac = zac->dalsi;
    }
    cout << endl;
}



void vypis2r(Node2 *zac) {  // Vypis dvojsmerneho seznamu od konce

    while (zac->dalsi){
        zac = zac->dalsi;
    }

    while (zac) {
        cout << zac->cislo << " ";
        zac = zac->back;
    }
    cout << endl;
}


Node1 *vypustLiche(Node1 *zac) {  //Vypusti vsechna licha cisla ze seznamu
    Node1 *tmp, *aktualni, *predchozi;

    predchozi = NULL;
    aktualni = zac;

    while (aktualni) {
        if (aktualni->cislo % 2 != 0) {
            tmp = aktualni->dalsi;

            if (predchozi != NULL) {
                predchozi->dalsi = tmp;
            } else {
                zac = tmp;
                predchozi = NULL;
            }

            delete aktualni;
            aktualni = tmp;
        } else {
            predchozi = aktualni;
            aktualni = aktualni->dalsi;
        }

    }
    return zac;
}

Node1 *vlozZaSude(Node1 *zac) { //Rozsireny seznam 2x za kazde sude cislo
    Node1 *aktualni = zac;
    Node1 *tmp = NULL;

    while (aktualni) {
        if (aktualni->cislo % 2 == 0) {
            tmp = new Node1(((aktualni->cislo)*2), aktualni->dalsi);
            aktualni->dalsi = tmp;
            aktualni = (aktualni->dalsi) ? aktualni->dalsi->dalsi : NULL;
        } else aktualni = aktualni->dalsi;
    }

    return zac;
}


Node1 *presunMax(Node1* zac) {  //Presune nejvetsi cislo na konec seznamu
    Node1* max = zac;
    Node1* aktualni = zac;
    Node1* prvni = zac;
    Node1* predMax = NULL;
    Node1* predchozi = NULL;

    while (aktualni) {
        if (aktualni->cislo > max->cislo) {
            max = aktualni;
            predMax = predchozi;
        }
        predchozi = aktualni;
        aktualni = aktualni->dalsi;
    }

    if (!predMax) prvni = max->dalsi;
    else predMax->dalsi = max->dalsi;

    predchozi->dalsi = max;
    max->dalsi = NULL;

    return prvni;

}

Node1 *presunMin(Node1 *zac) {  //Presune nejmensi cislo na zacatek seznamu
    Node1* min = zac;
    Node1* beforeMin = NULL;
    Node1* predchozi = NULL;
    Node1* aktualni = zac;
    Node1* prvni = zac;

    while (aktualni) {
        if (aktualni->cislo < min->cislo) {
            min = aktualni;
            beforeMin = predchozi;
        }
        predchozi = aktualni;
        aktualni = aktualni->dalsi;
    }
    if (beforeMin) {
        beforeMin->dalsi = min->dalsi;
        min->dalsi = zac;
        prvni = min;
    }

    return prvni;
}


Node2 *vypustLiche2(Node2 *zac) {  // Vypusti vsechny licha cisla z obousmerneho seznamu
    Node2* prvni = zac;
    while (zac) {
        if (zac->cislo % 2 > 0) {
            if (zac->back == NULL) {
                prvni = zac->dalsi;
                zac->dalsi->back = NULL;
            } else zac->back->dalsi = zac->dalsi;

            if (zac->dalsi == NULL) {
                zac->back->dalsi = NULL;
            } else zac->dalsi->back = zac->back;
            Node2* tmp = zac;
            zac = zac->dalsi;
            delete tmp;
        } else zac = zac->dalsi;
    }
    return prvni;
}