---

#include <iostream>
#include <random>
#include <ctime>
#include <cstdlib>
using namespace std;

struct tochd
{
    int inf;
    tochd *left;
    tochd *rigth;
};

void NewOchd(tochd **sl, tochd **sr)
{
    *sl = new tochd;
    *sr = new tochd;
    (*sl)->left = NULL;
    (*sl)->rigth = *sr;
    (*sr)->left = *sl;
    (*sr)->rigth = NULL;
}

void AddOchdLeft(tochd *sp, int inf)
{
    tochd *spt = new tochd;
    spt->inf = inf;
    spt->left = sp->left;
    spt->rigth = sp;
    spt->left->rigth = spt;
    sp->left = spt;
}

void AddOchdRigth(tochd *sp, int inf)
{
    tochd *spt = new tochd;
    spt->inf = inf;
    spt->left = sp;
    spt->rigth = sp->rigth;
    sp->rigth = spt;
    spt->rigth->left = spt;
}

int ReadOchdD(tochd *sp)
{
    int inf = sp->inf;
    sp->left->rigth = sp->rigth;
    sp->rigth->left = sp->left;
    delete sp;
    return inf;
}

void PrintList(tochd *sl, tochd *sr)
{
    tochd *p = sl->rigth;
    if (p == sr)
    {
        cout << "Список пуст";
        return;
    }
    while (p != sr)
    {
        cout << p->inf << " ";
        p = p->rigth;
    }
}

void DelOchdAll(tochd **sl, tochd **sr)
{
    tochd *spt = (*sl)->rigth;
    while (spt != *sr)
    {
        spt = (*sl)->rigth;
        ReadOchdD(spt);
    }
    delete *sl;
    delete *sr;
    *sl = NULL;
    *sr = NULL;
}

void div2Ochd(tochd *sl, tochd *sr, tochd **slL, tochd **srL, tochd **slR, tochd **srR)
{
    NewOchd(slL, srL);
    NewOchd(slR, srR);
    tochd *spt = sl->rigth;
    while (spt != sr)
    {
        AddOchdLeft(*srL, ReadOchdD(spt));
        spt = sl->rigth;
        if (spt != sr)
        {
            AddOchdLeft(*srR, ReadOchdD(spt));
            spt = sl->rigth;
        }
    }
    delete sl;
    delete sr;
}

void slipOchd(tochd **sl, tochd **sr, tochd *slL, tochd *srL, tochd *slR, tochd *srR)
{
    NewOchd(sl, sr);
    tochd *sptL = slL->rigth;
    tochd *sptR = slR->rigth;
    while ((sptL != srL) && (sptR != srR))
    {
        if (sptL->inf < sptR->inf)
        {
            AddOchdLeft(*sr, ReadOchdD(sptL));
            sptL = slL->rigth;
        }
        else
        {
            AddOchdLeft(*sr, ReadOchdD(sptR));
            sptR = slR->rigth;
        }
    }

    while (sptL != srL)
    {
        AddOchdLeft(*sr, ReadOchdD(sptL));
        sptL = slL->rigth;
    }
    delete slL;
    delete srL;

    while (sptR != srR)
    {
        AddOchdLeft(*sr, ReadOchdD(sptR));
        sptR = slR->rigth;
    }
    delete slR;
    delete srR;
}

void SotrSlipOchd(tochd **sl, tochd **sr)
{
    tochd *slL, *srL, *slR, *srR;
    if ((*sl)->rigth->rigth == *sr) return;

    div2Ochd(*sl, *sr, &slL, &srL, &slR, &srR);
    SotrSlipOchd(&slL, &srL);
    SotrSlipOchd(&slR, &srR);
    slipOchd(sl, sr, slL, srL, slR, srR);
}

int SearchPos(tochd *sl, tochd *sr, int key)
{
    int pos = 1;
    for (tochd *p = sl->rigth; p != sr; p = p->rigth, ++pos)
    {
        if (p->inf == key) return pos;
    }
    return -1;
}

tochd *FindMinNode(tochd *sl, tochd *sr)
{
    if (sl->rigth == sr) return NULL;
    tochd *mn = sl->rigth;
    for (tochd *p = mn->rigth; p != sr; p = p->rigth)
    {
        if (p->inf < mn->inf) mn = p;
    }
    return mn;
}

tochd *FindMaxNode(tochd *sl, tochd *sr)
{
    if (sl->rigth == sr) return NULL;
    tochd *mx = sl->rigth;
    for (tochd *p = mx->rigth; p != sr; p = p->rigth)
    {
        if (p->inf > mx->inf) mx = p;
    }
    return mx;
}

void DetachNode(tochd *node)
{
    node->left->rigth = node->rigth;
    node->rigth->left = node->left;
}

void InsertExistingBeforeTail(tochd *sr, tochd *node)
{
    node->left = sr->left;
    node->rigth = sr;
    sr->left->rigth = node;
    sr->left = node;
}

void DeleteNode(tochd *node)
{
    DetachNode(node);
    delete node;
}

void BuildList(tochd **sl, tochd **sr, int a[], int n)
{
    NewOchd(sl, sr);
    for (int i = 0; i < n; i++)
    {
        AddOchdLeft(*sr, a[i]);
    }
}

void PrintHeader(const char *text)
{
    cout << text << endl;
}

void Task4(tochd **sl, tochd **sr)
{
    tochd *sl2, *sr2;
    NewOchd(&sl2, &sr2);

    tochd *mx = FindMaxNode(*sl, *sr);
    if (mx != NULL)
    {
        tochd *p = mx->rigth;
        while (p != *sr)
        {
            tochd *next = p->rigth;
            DetachNode(p);
            InsertExistingBeforeTail(sr2, p);
            p = next;
        }
    }

    PrintHeader("Первый список после переноса:");
    PrintList(*sl, *sr);
    cout << endl;

    PrintHeader("Второй список:");
    PrintList(sl2, sr2);
    cout << endl;

    DelOchdAll(sl, sr);
    DelOchdAll(&sl2, &sr2);
}

void Task9(tochd **sl, tochd **sr)
{
    tochd *mn = FindMinNode(*sl, *sr);
    if (mn != NULL)
    {
        if (mn->left == *sl || mn->rigth == *sr)
        {
            DeleteNode(mn);
        }
        else
        {
            DeleteNode(mn->left);
            DeleteNode(mn->rigth);
        }
    }

    PrintHeader("Список после удаления:");
    PrintList(*sl, *sr);
    cout << endl;

    DelOchdAll(sl, sr);
}

void Task11(tochd **sl, tochd **sr)
{
    int values[100];
    int counts[100];
    int n = 0;

    for (tochd *p = (*sl)->rigth; p != *sr; p = p->rigth)
    {
        values[n] = p->inf;
        counts[n] = 0;
        n++;
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (values[i] == values[j]) counts[i]++;
        }
    }

    tochd *p = (*sl)->rigth;
    while (p != *sr)
    {
        tochd *next = p->rigth;
        bool remove = false;
        for (int i = 0; i < n; i++)
        {
            if (p->inf == values[i] && counts[i] > 1)
            {
                remove = true;
                break;
            }
        }
        if (remove) DeleteNode(p);
        p = next;
    }

    PrintHeader("Список после удаления повторяющихся значений:");
    PrintList(*sl, *sr);
    cout << endl;

    DelOchdAll(sl, sr);
}

int main()
{
    srand(time(0));

    const int N = 10;
    int a[N];
    for (int i = 0; i < N; i++)
    {
        a[i] = rand() % 101 - 50;
    }

    tochd *sl, *sr;
    BuildList(&sl, &sr, a, N);

    PrintHeader("Исходный список:");
    PrintList(sl, sr);
    cout << endl;

    SotrSlipOchd(&sl, &sr);

    PrintHeader("Отсортированный список:");
    PrintList(sl, sr);
    cout << endl;

    const int variantKey = 4;
    int pos = SearchPos(sl, sr, variantKey);
    if (pos != -1)
    {
        cout << "Элемент " << variantKey << " найден, порядковый номер: " << pos << endl;
    }
    else
    {
        cout << "Элемент " << variantKey << " не найден" << endl;
    }

    Task4(&sl, &sr);

    return 0;
}