Учебная версия на русском. Код и его вывод сохранены в исходном виде.

Разворот связного списка на C

Разверните связи односвязного списка за O(N) и освободите все узлы.

Постройте список из N целых через malloc. Реализуйте reverse_list, меняющую связи на месте с помощью prev, curr и next. Верните новую голову, выведите значения в обратном порядке и освободите память.

Не копируйте данные во вспомогательный массив. Каждый узел должен посещаться один раз; число дополнительных указателей постоянно. Проверяйте успешность выделения перед записью.

Ввод

Первая строка: N. Вторая: N целых через пробел.

Вывод

Одна строка со значениями развёрнутого списка через пробел.

Ограничения

1 <= N <= 100
-10000 <= значение <= 10000
O(N) времени и O(1) дополнительной памяти для разворота.
Узлы выделяются через malloc и полностью освобождаются.

Подсказки

Сохраните curr->next до перезаписи связи.
В конце curr равен NULL, а prev указывает на новую голову.

Код C

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *next;
};

// Reverses singly linked list in-place and returns new head
struct Node* reverse_list(struct Node *head) {
    // TODO: Implement iterative 3-pointer reversal (prev, curr, next)
    return NULL;
}

int main(void) {
    int n;
    if (scanf("%d", &n) != 1 || n <= 0) return 1;

    struct Node *head = NULL;
    struct Node *tail = NULL;

    for (int i = 0; i < n; i++) {
        int val;
        scanf("%d", &val);
        struct Node *new_node = (struct Node *)malloc(sizeof(struct Node));
        new_node->data = val;
        new_node->next = NULL;

        if (head == NULL) {
            head = new_node;
            tail = new_node;
        } else {
            tail->next = new_node;
            tail = new_node;
        }
    }

    head = reverse_list(head);

    struct Node *curr = head;
    while (curr != NULL) {
        printf("%d%s", curr->data, (curr->next == NULL) ? "" : " ");
        struct Node *temp = curr;
        curr = curr->next;
        free(temp);
    }
    printf("\n");

    return 0;
}

Открыть в компиляторе

Решение и объяснение

Начните с prev = NULL и curr = head. На каждом шаге сохраните next = curr->next, запишите curr->next = prev, затем выполните prev = curr и curr = next.

Для списка 1 → 2 → 3 сначала получается 1 → NULL, затем 2 → 1 и наконец 3 → 2 → 1. Указатель на необработанную часть нельзя терять.

При освобождении также сохраняйте следующий узел до free. Чтение node->next после free(node) недопустимо. Разворот требует O(1) дополнительной памяти, а исходные узлы по-прежнему занимают O(N).

Код решения

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *next;
};

struct Node* reverse_list(struct Node *head) {
    struct Node *prev = NULL;
    struct Node *curr = head;
    struct Node *next = NULL;

    while (curr != NULL) {
        // 1. Store next node before breaking link
        next = curr->next;
        // 2. Reverse current node pointer
        curr->next = prev;
        // 3. Move prev and curr forward one step
        prev = curr;
        curr = next;
    }

    return prev; // prev is the new head of the reversed list
}

int main(void) {
    int n;
    if (scanf("%d", &n) != 1 || n <= 0) return 1;

    struct Node *head = NULL;
    struct Node *tail = NULL;

    for (int i = 0; i < n; i++) {
        int val;
        scanf("%d", &val);
        struct Node *new_node = (struct Node *)malloc(sizeof(struct Node));
        new_node->data = val;
        new_node->next = NULL;

        if (head == NULL) {
            head = new_node;
            tail = new_node;
        } else {
            tail->next = new_node;
            tail = new_node;
        }
    }

    head = reverse_list(head);

    struct Node *curr = head;
    while (curr != NULL) {
        printf("%d%s", curr->data, (curr->next == NULL) ? "" : " ");
        struct Node *temp = curr;
        curr = curr->next;
        free(temp);
    }
    printf("\n");

    return 0;
}

Частые вопросы

Почему код и вывод остаются на английском?

Ключевые слова, идентификаторы и строки, проверяемые тестами, сохранены, чтобы не менять программу. Объяснения и элементы управления переведены.