#include <iostream>
 
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;
}