struct Data
{
    int a;
};

struct List
{
    Data d;
    List * next;
};

// Рекурсия, инверсия списка
List * reverse(List *u)
{
        if (u == 0) return 0;
        if (u->next == 0) return u;

        List * tmp = reverse(u->next);

        u->next->next = u;
        u->next = 0;
        return tmp;
}

// Находим значения списка
bool Find_Item_Single_List(List * u, int DataItem)
{
    List *ptr;
    ptr = u;

    while (ptr != NULL)
    {
        if (DataItem == ptr->d.a) return true;
        else ptr = ptr->next;
    }

    return false;
}

int main(int argc, char** argv)
{
    List *u = NULL;

    // 1-й узел
    u = new List; // Объявление
    u->d.a = 3;
    u->next = NULL; // Указатель на следующий элемент
    // Для удобства создаем переменную-указатель, которая хранит адрес последнего элемента
    List *x;

    // 2-й узел
    x = u;
    x->next = new List;
    x = x->next;
    x->d.a = 5;
    x->next = NULL;
    //
    List *c;

    // 3-й узел
    c = x;
    c->next = new List;
    c = c->next;
    c->d.a = 1;
    c->next = NULL;
    //
    List *b;

    // 4-й узел
    b = c;
    b->next = new List;
    b = b->next;
    b->d.a = 9;
    b->next = NULL;

    // Вывод (просто идем по списку)
    while(u)
    {
        cout << u->d.a << endl;
        u = u->next;
    }

    reverse(u);

    return 0;
}