Инверсия однонаправленного списка

Условие

Дан однонаправленный список, реализованный через структуру Node. Требуется изменить порядок элементов списка на обратный и вернуть указатель на новую голову.

struct Node {
    int value;
    Node* nxt;

    Node() : value(0), nxt(nullptr) {}
    Node(int x) : value(x), nxt(nullptr) {}
    Node(int x, Node* nxt) : value(x), nxt(nxt) {}
};

Node* ReverseList(Node* root) {
    // реализовать разворот списка
}

Пример:

Вход: 1 → 2 → 3 → nullptr
Выход: 3 → 2 → 1 → nullptr

Ответ

Последовательно перенаправляйте nxt каждого узла на предыдущий, заранее сохраняя следующий. После завершения предыдущий узел становится новой головой.

Node* ReverseList(Node* root) {
    Node* previous = nullptr;
    while (root) {
        Node* next = root->nxt;
        root->nxt = previous;
        previous = root;
        root = next;
    }
    return previous;
}

Пустой список даёт nullptr, одноэлементный остаётся тем же. Время O(n), память O(1), новых узлов нет. Предполагается отсутствие циклов; внешние указатели продолжают указывать на прежние узлы, но направление связей изменено.