Здравствуйте, Erop, Вы писали:

MMN>>Идём по списку и меняем направление связей на противоположное. Если в конце доходим до изначального головного элемента, то цикл есть, иначе — нет. Для восстановления списка проходим по нему в обратную сторону и снова меняем направление связей на противоположное.

E>В случае цикла

E>1) трудно восстановить оригинальный список

Не труднее, чем испортить.

E>2) трудно доказать отсутствие потерь памяти, в случае если цикл есть

Цепочка связей не разрывается, т.ч. ничего не теряется.

Вот реализация:

#include <cstddef>
#include <cassert>
#include <vector>


struct node
{
    node *next;
};

// Returns new head
node *reverse(node *head)
{
    node *cur = head;
    node *prev = NULL;
    while (cur != NULL)
    {
        node *const t = cur->next;
        cur->next = prev;
        prev = cur;
        cur = t;
    }

    return prev;
}

bool is_there_loop(node *head)
{
    if (head == NULL || head->next == NULL)
        return false;

    node *const new_head = reverse(head);
    reverse(new_head);

    return new_head == head;
}

void print(const std::vector<node> &nodes)
{
    printf("{");
    for (size_t i = 0, i_max = nodes.size(); i < i_max; ++i)
    {
        if (i > 0)
            printf(", ");
        printf("0x%p {next = 0x%p}", &nodes[i], nodes[i].next);
    }
    printf("}\n");
}

void check_loop(std::vector<node> &nodes, bool expectation)
{
    print(nodes);

    const bool result = is_there_loop(nodes.empty() ? NULL: &nodes[0]);
    assert(result == expectation);

    print(nodes);
    printf("is_there_loop = %s\n\n", result ? "true": "false");
}

int main()
{
    std::vector<node> nodes;

    nodes.resize(0);
    check_loop(nodes, false);

    nodes.resize(1);
    nodes[0].next = NULL;
    check_loop(nodes, false);

    nodes.resize(1);
    nodes[0].next = &nodes[0];
    check_loop(nodes, true);

    nodes.resize(2);
    nodes[0].next = &nodes[1];
    nodes[1].next = NULL;
    check_loop(nodes, false);

    // на поиграться
    nodes.resize(3);
    nodes[0].next = &nodes[1];
    nodes[1].next = &nodes[2];
    nodes[2].next = &nodes[1];
    check_loop(nodes, true);

    return 0;
}

Выводится:

{}
{}
is_there_loop = false

{0x00370850 {next = 0x00000000}}
{0x00370850 {next = 0x00000000}}
is_there_loop = false

{0x00370850 {next = 0x00370850}}
{0x00370850 {next = 0x00370850}}
is_there_loop = true

{0x00370880 {next = 0x00370884}, 0x00370884 {next = 0x00000000}}
{0x00370880 {next = 0x00370884}, 0x00370884 {next = 0x00000000}}
is_there_loop = false

{0x003708B8 {next = 0x003708BC}, 0x003708BC {next = 0x003708C0}, 0x003708C0 {next = 0x003708BC}}
{0x003708B8 {next = 0x003708BC}, 0x003708BC {next = 0x003708C0}, 0x003708C0 {next = 0x003708BC}}
is_there_loop = true