TestList

#include <iostream>
using namespace std;

int n;
struct node
{
    int val;
    node *next;
    node *prev;
};

void AddNodeToStartList(node * firstNode, node *newNode)
{
    newNode->prev = firstNode->prev;
    newNode->next = firstNode;
    firstNode->prev->next = newNode;
    firstNode->prev = newNode;
}
void AddNodeToEndList(node *endNode, node *newNode)
{
     newNode->next = endNode->next;
     newNode->prev = endNode;
     endNode->next->prev = newNode;
     endNode->next = newNode;
}

node *AddValueToStartList (node *firstNode, int value)
{
    node *prevNode = new node();
    prevNode->val = value;
    AddNodeToStartList(firstNode, prevNode);
    return firstNode;
}

node *AddValueToEndList (node *endNode, int value)
{
    node *nextNode = new node();
    nextNode->val = value;
    AddNodeToStartList(endNode, nextNode);
    return endNode;
}

node *CreateListFromValue(int value)
{
    node *Node = new node();
    Node->val = value;
    Node->next = Node;
    Node->prev = Node;
    return Node;
}


void PrintList(node * Node)
{
    node *endNode = Node;
    node *currentNode = Node;
    
    cout << "My current list is:" << endl;
    do
    {
        cout << currentNode->val;
        cout << ",";
        currentNode = currentNode->next;
    }while (endNode != currentNode);
    
    cout << endl;
}


void sort(node * firstNode, node *endNode)
{
    node *First = firstNode;
    node *currentNode = firstNode;
    node *currentNodeNext = firstNode->next;
    node *y = firstNode;
    node *p = firstNode;//граница
    node *x = firstNode;//сравниваемое значение
    while (currentNode != endNode)
    {
        if (firstNode == endNode) return;
        if ((currentNode == First)&&(currentNode->val > currentNodeNext->val))
        {
            //Обмен указателей при p = First
            currentNode->next = currentNodeNext->next;
            currentNodeNext->prev = currentNode->prev;
            currentNode->prev->next = currentNodeNext;
            currentNodeNext->next->prev = currentNode;
            currentNode->prev = currentNodeNext;
            currentNodeNext->next = currentNode;
            First = currentNodeNext;
        }
        if (y <= x)
        {
            x = x->next;
        }
        
        if (y->prev <= x)
        {
            y = y->prev;
        }
        
        if ((y > x)&&(y->prev < x))
        {
            x->next->prev = x->prev;
            x->prev->next = x->next;
            
            x->next = y;
            x->prev = y->prev;
            y->prev->next = x;
            y->prev = x;
            
        }
    }
}


/*
void sort(node *root){
    node *p, *key;
    node *result = root;
    root = root->next;       Головой стал следующий элемент
    result->next = NULL;     Первый элемент отсортированного списка 

    while(root->next != NULL){
        key = root;
        root = root->next;
        if(key->val < result->val){    Вставляем результат в голову 
            key->next = result;
            result = key;
        }else
        {
            p = result;
            while(p->next != NULL){      Бежим по уже сформированному результату
                if(p->next->val > key->val)
                    break;
                p = p->next;
            }
            key->next = p->next;
            p->next = key;
        }
    }
    root = result;
}*/

int main() {

    
    node *firstNode;
    node *endNode;
    int choose;
    int q;
    
    cout << "1)Создать список со значением\n";
    cout << "2)Добавить значение в начало списка\n";
    cout << "3)Добавить значение в конец списка\n";
    cout << "4)Показать список\n";
    cout << "5)Сортировать список\n";
    cin >> choose;
    switch(choose)
    {
        case 1:
        {
            cout << "Введите значение для добавления в созданый список\n";
            cin >> q;
            node *Node = CreateListFromValue(q);
        };
        case 2:
        {
            cout << "Введите значение для добавления в начало списка\n";
            cin >> q;
            firstNode = AddValueToStartList(firstNode, q);
        };
        case 3:
        {
            cout << "Введите значение для добавления в конец списка\n";
            cin >> q;
            endNode = AddValueToEndList(endNode, q);
        };
        case 4:
        {
            PrintList(firstNode);
        };
        case 5:
        {
            sort(firstNode, endNode);
        };
    }
    
    // Initial node creation
    /*PrintList(firstNode);
    node *First = firstNode;
    
    // Creating next nodes
    node *lastNode = AddValueToList(firstNode, 2);
   // lastNode = AddValueToList(lastNode, 3);
   // lastNode = AddValueToList(lastNode, 1);
    PrintList(firstNode);
    */
    //sort(firstNode);
    /*if (firstNode != NULL)
    {
    cout << "Sorted List" << endl;
    PrintList(firstNode);
    }*/
    
    
    
    cout << "Hello World!";
    return 0;
}