#include <iostream>
#include <string>
#include <limits>


struct SOListNode
{
    int value;
    SOListNode* next;
};


class SOList
{
    SOListNode* init;
    SOListNode* term;

public:
    SOList()
    {
        init = new SOListNode;
        term = new SOListNode;
        init->next = term;
        term->next = 0;
    }

    ~SOList()
    {
        SOListNode *n1, *n2;
        n1 = init;
        while (n1 != 0) {
            n2 = n1->next;
            delete n1;
            n1 = n2;
        }
    }

    void transpose(SOListNode* node)
    {
        if (node == init->next)
            return;
        SOListNode* after = node->next;
        SOListNode* this_node = new SOListNode;
        while (init->next != node)
        {
            if (init->next->next == node)
            {
                this_node = init->next;
                break;
            }
            init->next = init->next->next;
        }
        this_node->next = node->next;
        node->next = init->next;
        init->next= node;
    }

    void print(int K) const
    {
        SOListNode* node = init->next;
        std::cout << "{ ";
        while (node != term && K > 0) {
            std::cout << node->value << " ";
            node = node->next;
            --K;
        }
        std::cout << "}" << std::endl;
    }

    SOListNode* find(int k)
    {
        SOListNode* node = init->next;
        while (node != term) {
            if (node->value == k)
            {
                transpose(node);
                break;
            }
            node = node->next;
        }
        if (node == term)
            return 0;

        return node;
    }

    SOListNode* insert(int k)
    {
        SOListNode* new_tail = new SOListNode;
        new_tail->value = k;
        while (init->next != term)
            {
                init = init->next;
            }
        init->next = new_tail;
        new_tail->next = term;
        return new_tail;
    }

    void erase(SOListNode* node)
    {
        if (node == init || node == term)
            return;
        SOListNode* after = node->next;
        SOListNode* this_node = init;
        delete node;
        while (this_node->next != node)
        {
            this_node = this_node->next;
        }
        this_node->next = after;
    }

    bool compare(SOList& node)
    {
        bool b1=false;
        bool b2=false;
        SOListNode* n1 = init->next;
        SOListNode* n2 = (node.init)->next;

                while (n1 != term)
                {
                    if (node.find((*n1).value))
                        b1 = true;
                    else
                        b1 = false;
                        break;
                    n1 = n1->next;
                }
                while (n2 != node.term)
                {
                    if (find((*n2).value))
                        b2 = true;
                    else
                        b2 = false;
                        break;
                    n2 = n2->next;
                }

            if(b1==true && b2==true)
                return true;
        return false;

    }
};

int main()
{
    SOList l;
    l.insert(1);
    l.insert(2);
    l.insert(3);
    l.insert(4);
    l.insert(5);
    l.print(10);
    return 0;
}