
#include 

using namespace std;

struct Item;

struct List
{
    Item * first;
    Item * last;
};

struct Item
{
    string name;
    Item * next;
};

void init (List & a)
{
    a.first = nullptr;
    a.last = nullptr;
}


void insertFirst (List & a, string name0)
{
   Item * p = new Item;
   p-> name = name0;
   p->next = a.first;
   a.first = p;
   if (a.last==nullptr)
      a.last = p;
}

void insertLast (List & a, string name0)
{
   Item * p = new Item;
   p->name = name0;

   p->next = nullptr;
   if (a.last == nullptr)
   {
       a.first = p;
   }
   else
   {
       a.last -> next = p;
   }
   a.last = p;
}

void tisk(List & a)
{
  cout << "[" << endl;
  Item * p = a.first;
  while (p != nullptr)
  {
      cout << p->name << endl;
      p= p->next;
  }
  cout << "]" << endl << endl;
}

int main()
{
    List b;

    init(b);
    insertFirst(b,"Kacenka");
    insertFirst(b,"Lucka");
    insertFirst(b,"Honza");
    tisk (b);

    
    return 0;
}


void insert (List & a, string name0)
{
   Item * p = new Item;
   p->name = name0;
   p->next = nullptr;

   Item * t = a.first;
   Item * u = nullptr;
   while (t != nullptr && t->name < p->name)
   {
       u = t;
       t = t->next;
   }

   if (t != nullptr)
   {
       // vlozit p pred t
       if (u != nullptr)
          u->next = p;
       else
          a.first = p;
       p->next = t;
   }
   else
   {
       if (a.first == nullptr)
           a.first = p;
       else
           a.last->next = p;
       a.last = p;
   }
}

int main()
{
    List b;


    init(b);
    insert (b,"Milos");
    insert (b,"Kacenka");
    insert (b,"Lucka");
    insert (b,"Honza");
    insert (b,"Anicka");
    tisk (b);

    List c;
    init(c);

    while (b.first != nullptr)
    {
       Item * t = unlinkFirst(b);
       linkFirst(c,t);
    }
    tisk (b);
    tisk(c);

    
    return 0;
}