#include<iostream>
#include<cstdlib>
#include<ctime>
 
struct Node
{
    int key;
    struct Node *prev;
    struct Node *next;
};
 
struct List
{
    struct Node *head;
    struct Node *tail;
};
 
void ListInit(struct List &L)
{
    L.head = nullptr;
    L.tail = nullptr;
}
 
bool ListIsEmpty(struct List L)
{
    return (L.head == nullptr && L.tail == nullptr);
}
 
Node *ListSearch(struct List L,int k)
{
    Node *x = L.head;
    while(x != nullptr && x->key != k)
        x = x->next;
    return x;
}
 
void ListInsert(struct List &L,int k)
{
    Node *x = new Node;
    x->key = k;
    x->next = L.head;
    if(L.head != nullptr)
        L.head->prev = x;
    L.head = x;
    x->prev = nullptr;
    if(x->next == nullptr)
        L.tail = x;
}
 
void ListDelete(struct List &L,int k)
{
    Node *x = ListSearch(L,k);
    if(x != nullptr)
    {
        if(x->next == nullptr)
            L.tail = x->prev;
        if(x->prev != nullptr)
            x->prev->next = x->next;
        else
            L.head = x->next;
        if(x->next != nullptr)
            x->next->prev = x->prev;
        delete x;
    }
}
 
void ListDispayForward(struct List L)
{
    int counter = 0;
    struct Node *p = L.head;
    while(p != nullptr)
    {
        std::cout<<p->key<<" -> ";
        p = p->next;
        counter++;
    }
    std::cout<<"NULL \n";
    std::cout<<"Liczba wezlow listy : "<< counter <<'\n';
}
 
void ListDispayBackward(struct List L)
{
    int counter = 0;
    struct Node *p = L.tail;
    while(p != nullptr)
    {
        std::cout<<p->key<<" -> ";
        p = p->prev;
        counter++;
    }
    std::cout<<"NULL \n";
    std::cout<<"Liczba wezlow listy : "<< counter <<'\n';
}
 
 
void ListSplit(struct List L, struct List &L1,struct List &L2)
{
    struct Node *p,*q;
    //Wyszukiwanie srodkowego wezła
    //Iterujemy wskaźniki z obu stron i gdy się spotkaja to oznacza ze znaleźlismy węzeł
    //Pętla while sprawdza dwa warunki dla list o parzystej i nieparzystej liczbie węzłów
    p = L.head;
    q = L.tail;
    while(p != q && p->next != q)
    {
        p = p->next;
        q = q->prev;
    }
    //Po znalezieniu węzła rozdzielamy listę za znalezionym węzłem
    if(p == nullptr && p->next == nullptr)
    {
        L1.head = L.head;
        L1.tail = L.tail;
        L2.head = nullptr;
        L2.tail = nullptr;
    }
    else
    {
        q = p->next;
        p->next = nullptr;
        q->prev = nullptr;
        L1.head = L.head;
        L1.tail = p;
        L2.head = q;
        L2.tail = L.tail;
    }
}
 
void ListMerge(struct List &L, struct List L1,struct List L2)
{
    struct Node *curr;
    //Sprawdzamy czy któraś z list jest pusta i zwracamy tę niepustą
    if(ListIsEmpty(L1))
        L.head = L2.head;
    else if(ListIsEmpty(L2))
        L.head = L1.head;
    else
    {
        // Ustawiamy głowę dla listy wynikowej
 
        if(L2.head->key < L1.head->key)
        {
            L.head = L2.head;
            L.tail = L2.head;
            L2.head = L2.head->next;
        }
        else
        {
            L.head = L1.head;
            L.tail = L1.tail;
            L1.head = L1.head->next;
        }
        curr = L.head;
        L.head->prev = nullptr;
        // Iterujemy wskaźniki dopóki nie osiągniemy końca co najmniej jednej z list
        // dołączając do listy wynikowej węzeł o mniejszym lub równym kluczu
        while(L1.head != nullptr && L2.head != nullptr)
        {
            if(L2.head->key < L1.head->key)
            {
                curr->next = L2.head;
                L2.head->prev = curr;
                L2.head = L2.head->next;
            }
            else
            {
                curr->next = L1.head;
                L1.head->prev = curr;
                L1.head = L1.head->next;
            }
            curr = curr->next;
        }
        //Dołączenie reszty listy do listy wynikowej
        if(L1.head != nullptr)
        {
            curr->next = L1.head;
            L1.head->prev = curr;
            L.tail = L1.tail;
        }
        else
        {
            curr->next = L2.head;
            L2.head->prev  = curr;
            L.tail = L2.tail;
        }
    }
}
 
void ListMergeSort(struct List &L)
{
    struct List h1,h2;
    if(L.head != nullptr && L.head->next != nullptr)
    {
        ListSplit(L,h1,h2);
        ListMergeSort(h1);
        ListMergeSort(h2);
        ListMerge(L,h1,h2);
    }
}
 
int main()
{
    int k,n,m,p;
    List L;
    ListInit(L);
    srand(time(nullptr));
        std::cout<<"Ile liczb wylosowac \n";
        std::cin>>n;
        std::cout<<"Podaj gorny zakres przedzialu dla losowanych liczb \n";
        std::cin>>m;
        for(k = 1;k <= n;k++)
            ListInsert(L,rand()%m);
        std::cout<<"Lista L \n";
        ListDispayForward(L);
        ListDispayBackward(L);
        ListMergeSort(L);
        std::cout<<"Lista L \n";
        ListDispayForward(L);
        ListDispayBackward(L);
        while(!ListIsEmpty(L))
            ListDelete(L,L.head->key);
        //system("PAUSE");
    return 0;
}
 

I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPGNzdGRsaWI+CiNpbmNsdWRlPGN0aW1lPgoKc3RydWN0IE5vZGUKewogICAgaW50IGtleTsKICAgIHN0cnVjdCBOb2RlICpwcmV2OwogICAgc3RydWN0IE5vZGUgKm5leHQ7Cn07CgpzdHJ1Y3QgTGlzdAp7CiAgICBzdHJ1Y3QgTm9kZSAqaGVhZDsKICAgIHN0cnVjdCBOb2RlICp0YWlsOwp9OwoKdm9pZCBMaXN0SW5pdChzdHJ1Y3QgTGlzdCAmTCkKewogICAgTC5oZWFkID0gbnVsbHB0cjsKICAgIEwudGFpbCA9IG51bGxwdHI7Cn0KCmJvb2wgTGlzdElzRW1wdHkoc3RydWN0IExpc3QgTCkKewogICAgcmV0dXJuIChMLmhlYWQgPT0gbnVsbHB0ciAmJiBMLnRhaWwgPT0gbnVsbHB0cik7Cn0KCk5vZGUgKkxpc3RTZWFyY2goc3RydWN0IExpc3QgTCxpbnQgaykKewogICAgTm9kZSAqeCA9IEwuaGVhZDsKICAgIHdoaWxlKHggIT0gbnVsbHB0ciAmJiB4LT5rZXkgIT0gaykKICAgICAgICB4ID0geC0+bmV4dDsKICAgIHJldHVybiB4Owp9Cgp2b2lkIExpc3RJbnNlcnQoc3RydWN0IExpc3QgJkwsaW50IGspCnsKICAgIE5vZGUgKnggPSBuZXcgTm9kZTsKICAgIHgtPmtleSA9IGs7CiAgICB4LT5uZXh0ID0gTC5oZWFkOwogICAgaWYoTC5oZWFkICE9IG51bGxwdHIpCiAgICAgICAgTC5oZWFkLT5wcmV2ID0geDsKICAgIEwuaGVhZCA9IHg7CiAgICB4LT5wcmV2ID0gbnVsbHB0cjsKICAgIGlmKHgtPm5leHQgPT0gbnVsbHB0cikKICAgICAgICBMLnRhaWwgPSB4Owp9Cgp2b2lkIExpc3REZWxldGUoc3RydWN0IExpc3QgJkwsaW50IGspCnsKICAgIE5vZGUgKnggPSBMaXN0U2VhcmNoKEwsayk7CiAgICBpZih4ICE9IG51bGxwdHIpCiAgICB7CiAgICAgICAgaWYoeC0+bmV4dCA9PSBudWxscHRyKQogICAgICAgICAgICBMLnRhaWwgPSB4LT5wcmV2OwogICAgICAgIGlmKHgtPnByZXYgIT0gbnVsbHB0cikKICAgICAgICAgICAgeC0+cHJldi0+bmV4dCA9IHgtPm5leHQ7CiAgICAgICAgZWxzZQogICAgICAgICAgICBMLmhlYWQgPSB4LT5uZXh0OwogICAgICAgIGlmKHgtPm5leHQgIT0gbnVsbHB0cikKICAgICAgICAgICAgeC0+bmV4dC0+cHJldiA9IHgtPnByZXY7CiAgICAgICAgZGVsZXRlIHg7CiAgICB9Cn0KCnZvaWQgTGlzdERpc3BheUZvcndhcmQoc3RydWN0IExpc3QgTCkKewogICAgaW50IGNvdW50ZXIgPSAwOwogICAgc3RydWN0IE5vZGUgKnAgPSBMLmhlYWQ7CiAgICB3aGlsZShwICE9IG51bGxwdHIpCiAgICB7CiAgICAgICAgc3RkOjpjb3V0PDxwLT5rZXk8PCIgLT4gIjsKICAgICAgICBwID0gcC0+bmV4dDsKICAgICAgICBjb3VudGVyKys7CiAgICB9CiAgICBzdGQ6OmNvdXQ8PCJOVUxMIFxuIjsKICAgIHN0ZDo6Y291dDw8IkxpY3piYSB3ZXpsb3cgbGlzdHkgOiAiPDwgY291bnRlciA8PCdcbic7Cn0KCnZvaWQgTGlzdERpc3BheUJhY2t3YXJkKHN0cnVjdCBMaXN0IEwpCnsKICAgIGludCBjb3VudGVyID0gMDsKICAgIHN0cnVjdCBOb2RlICpwID0gTC50YWlsOwogICAgd2hpbGUocCAhPSBudWxscHRyKQogICAgewogICAgICAgIHN0ZDo6Y291dDw8cC0+a2V5PDwiIC0+ICI7CiAgICAgICAgcCA9IHAtPnByZXY7CiAgICAgICAgY291bnRlcisrOwogICAgfQogICAgc3RkOjpjb3V0PDwiTlVMTCBcbiI7CiAgICBzdGQ6OmNvdXQ8PCJMaWN6YmEgd2V6bG93IGxpc3R5IDogIjw8IGNvdW50ZXIgPDwnXG4nOwp9CgoKdm9pZCBMaXN0U3BsaXQoc3RydWN0IExpc3QgTCwgc3RydWN0IExpc3QgJkwxLHN0cnVjdCBMaXN0ICZMMikKewogICAgc3RydWN0IE5vZGUgKnAsKnE7CiAgICAvL1d5c3p1a2l3YW5pZSBzcm9ka293ZWdvIHdlesWCYQogICAgLy9JdGVydWplbXkgd3NrYcW6bmlraSB6IG9idSBzdHJvbiBpIGdkeSBzacSZIHNwb3RrYWphIHRvIG96bmFjemEgemUgem5hbGXFumxpc215IHfEmXplxYIKICAgIC8vUMSZdGxhIHdoaWxlIHNwcmF3ZHphIGR3YSB3YXJ1bmtpIGRsYSBsaXN0IG8gcGFyenlzdGVqIGkgbmllcGFyenlzdGVqIGxpY3piaWUgd8SZesWCw7N3CiAgICBwID0gTC5oZWFkOwogICAgcSA9IEwudGFpbDsKICAgIHdoaWxlKHAgIT0gcSAmJiBwLT5uZXh0ICE9IHEpCiAgICB7CiAgICAgICAgcCA9IHAtPm5leHQ7CiAgICAgICAgcSA9IHEtPnByZXY7CiAgICB9CiAgICAvL1BvIHpuYWxlemllbml1IHfEmXrFgmEgcm96ZHppZWxhbXkgbGlzdMSZIHphIHpuYWxlemlvbnltIHfEmXrFgmVtCiAgICBpZihwID09IG51bGxwdHIgJiYgcC0+bmV4dCA9PSBudWxscHRyKQogICAgewogICAgICAgIEwxLmhlYWQgPSBMLmhlYWQ7CiAgICAgICAgTDEudGFpbCA9IEwudGFpbDsKICAgICAgICBMMi5oZWFkID0gbnVsbHB0cjsKICAgICAgICBMMi50YWlsID0gbnVsbHB0cjsKICAgIH0KICAgIGVsc2UKICAgIHsKICAgICAgICBxID0gcC0+bmV4dDsKICAgICAgICBwLT5uZXh0ID0gbnVsbHB0cjsKICAgICAgICBxLT5wcmV2ID0gbnVsbHB0cjsKICAgICAgICBMMS5oZWFkID0gTC5oZWFkOwogICAgICAgIEwxLnRhaWwgPSBwOwogICAgICAgIEwyLmhlYWQgPSBxOwogICAgICAgIEwyLnRhaWwgPSBMLnRhaWw7CiAgICB9Cn0KCnZvaWQgTGlzdE1lcmdlKHN0cnVjdCBMaXN0ICZMLCBzdHJ1Y3QgTGlzdCBMMSxzdHJ1Y3QgTGlzdCBMMikKewogICAgc3RydWN0IE5vZGUgKmN1cnI7CiAgICAvL1NwcmF3ZHphbXkgY3p5IGt0w7NyYcWbIHogbGlzdCBqZXN0IHB1c3RhIGkgendyYWNhbXkgdMSZIG5pZXB1c3TEhQogICAgaWYoTGlzdElzRW1wdHkoTDEpKQogICAgICAgIEwuaGVhZCA9IEwyLmhlYWQ7CiAgICBlbHNlIGlmKExpc3RJc0VtcHR5KEwyKSkKICAgICAgICBMLmhlYWQgPSBMMS5oZWFkOwogICAgZWxzZQogICAgewogICAgICAgIC8vIFVzdGF3aWFteSBnxYJvd8SZIGRsYSBsaXN0eSB3eW5pa293ZWoKCiAgICAgICAgaWYoTDIuaGVhZC0+a2V5IDwgTDEuaGVhZC0+a2V5KQogICAgICAgIHsKICAgICAgICAgICAgTC5oZWFkID0gTDIuaGVhZDsKICAgICAgICAgICAgTC50YWlsID0gTDIuaGVhZDsKICAgICAgICAgICAgTDIuaGVhZCA9IEwyLmhlYWQtPm5leHQ7CiAgICAgICAgfQogICAgICAgIGVsc2UKICAgICAgICB7CiAgICAgICAgICAgIEwuaGVhZCA9IEwxLmhlYWQ7CiAgICAgICAgICAgIEwudGFpbCA9IEwxLnRhaWw7CiAgICAgICAgICAgIEwxLmhlYWQgPSBMMS5oZWFkLT5uZXh0OwogICAgICAgIH0KICAgICAgICBjdXJyID0gTC5oZWFkOwogICAgICAgIEwuaGVhZC0+cHJldiA9IG51bGxwdHI7CiAgICAgICAgLy8gSXRlcnVqZW15IHdza2HFum5pa2kgZG9ww7NraSBuaWUgb3NpxIVnbmllbXkga2/FhGNhIGNvIG5ham1uaWVqIGplZG5laiB6IGxpc3QKICAgICAgICAvLyBkb8WCxIVjemFqxIVjIGRvIGxpc3R5IHd5bmlrb3dlaiB3xJl6ZcWCIG8gbW5pZWpzenltIGx1YiByw7N3bnltIGtsdWN6dQogICAgICAgIHdoaWxlKEwxLmhlYWQgIT0gbnVsbHB0ciAmJiBMMi5oZWFkICE9IG51bGxwdHIpCiAgICAgICAgewogICAgICAgICAgICBpZihMMi5oZWFkLT5rZXkgPCBMMS5oZWFkLT5rZXkpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGN1cnItPm5leHQgPSBMMi5oZWFkOwogICAgICAgICAgICAgICAgTDIuaGVhZC0+cHJldiA9IGN1cnI7CiAgICAgICAgICAgICAgICBMMi5oZWFkID0gTDIuaGVhZC0+bmV4dDsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGN1cnItPm5leHQgPSBMMS5oZWFkOwogICAgICAgICAgICAgICAgTDEuaGVhZC0+cHJldiA9IGN1cnI7CiAgICAgICAgICAgICAgICBMMS5oZWFkID0gTDEuaGVhZC0+bmV4dDsKICAgICAgICAgICAgfQogICAgICAgICAgICBjdXJyID0gY3Vyci0+bmV4dDsKICAgICAgICB9CiAgICAgICAgLy9Eb8WCxIVjemVuaWUgcmVzenR5IGxpc3R5IGRvIGxpc3R5IHd5bmlrb3dlagogICAgICAgIGlmKEwxLmhlYWQgIT0gbnVsbHB0cikKICAgICAgICB7CiAgICAgICAgICAgIGN1cnItPm5leHQgPSBMMS5oZWFkOwogICAgICAgICAgICBMMS5oZWFkLT5wcmV2ID0gY3VycjsKICAgICAgICAgICAgTC50YWlsID0gTDEudGFpbDsKICAgICAgICB9CiAgICAgICAgZWxzZQogICAgICAgIHsKICAgICAgICAgICAgY3Vyci0+bmV4dCA9IEwyLmhlYWQ7CiAgICAgICAgICAgIEwyLmhlYWQtPnByZXYgID0gY3VycjsKICAgICAgICAgICAgTC50YWlsID0gTDIudGFpbDsKICAgICAgICB9CiAgICB9Cn0KCnZvaWQgTGlzdE1lcmdlU29ydChzdHJ1Y3QgTGlzdCAmTCkKewogICAgc3RydWN0IExpc3QgaDEsaDI7CiAgICBpZihMLmhlYWQgIT0gbnVsbHB0ciAmJiBMLmhlYWQtPm5leHQgIT0gbnVsbHB0cikKICAgIHsKICAgICAgICBMaXN0U3BsaXQoTCxoMSxoMik7CiAgICAgICAgTGlzdE1lcmdlU29ydChoMSk7CiAgICAgICAgTGlzdE1lcmdlU29ydChoMik7CiAgICAgICAgTGlzdE1lcmdlKEwsaDEsaDIpOwogICAgfQp9CgppbnQgbWFpbigpCnsKICAgIGludCBrLG4sbSxwOwogICAgTGlzdCBMOwogICAgTGlzdEluaXQoTCk7CiAgICBzcmFuZCh0aW1lKG51bGxwdHIpKTsKICAgICAgICBzdGQ6OmNvdXQ8PCJJbGUgbGljemIgd3lsb3Nvd2FjIFxuIjsKICAgICAgICBzdGQ6OmNpbj4+bjsKICAgICAgICBzdGQ6OmNvdXQ8PCJQb2RhaiBnb3JueSB6YWtyZXMgcHJ6ZWR6aWFsdSBkbGEgbG9zb3dhbnljaCBsaWN6YiBcbiI7CiAgICAgICAgc3RkOjpjaW4+Pm07CiAgICAgICAgZm9yKGsgPSAxO2sgPD0gbjtrKyspCiAgICAgICAgICAgIExpc3RJbnNlcnQoTCxyYW5kKCklbSk7CiAgICAgICAgc3RkOjpjb3V0PDwiTGlzdGEgTCBcbiI7CiAgICAgICAgTGlzdERpc3BheUZvcndhcmQoTCk7CiAgICAgICAgTGlzdERpc3BheUJhY2t3YXJkKEwpOwogICAgICAgIExpc3RNZXJnZVNvcnQoTCk7CiAgICAgICAgc3RkOjpjb3V0PDwiTGlzdGEgTCBcbiI7CiAgICAgICAgTGlzdERpc3BheUZvcndhcmQoTCk7CiAgICAgICAgTGlzdERpc3BheUJhY2t3YXJkKEwpOwogICAgICAgIHdoaWxlKCFMaXN0SXNFbXB0eShMKSkKICAgICAgICAgICAgTGlzdERlbGV0ZShMLEwuaGVhZC0+a2V5KTsKICAgICAgICAvL3N5c3RlbSgiUEFVU0UiKTsKICAgIHJldHVybiAwOwp9Cg==

NTAgMTAwMA==

50 1000