Deutsche Lernausgabe

Einfach verkettete Liste in C umkehren

Richten Sie vorhandene Verknüpfungen mit drei Zeigern neu aus und geben Sie den neuen Listenkopf zurück.

Erstellen Sie aus den eingelesenen Ganzzahlen eine Liste. Die Funktion reverse_list soll die Verknüpfungen der vorhandenen Knoten umkehren und den neuen Kopf zurückgeben, ohne eine zweite Liste anzulegen.

Geben Sie nach der Ausgabe alle Knoten frei. Prüfen Sie jede Speicherreservierung: Ein fehlgeschlagenes malloc darf weder zur Dereferenzierung eines Nullzeigers noch zum Verlust bereits reservierter Knoten führen.

Eingabe

N, danach N Ganzzahlen in der ursprünglichen Listenreihenfolge.

Ausgabe

Die Werte der umgekehrten Liste in einer Zeile, durch Leerzeichen getrennt.

Vorgaben

1 ≤ N ≤ 100; Werte zwischen -10000 und 10000.
Umkehrung in O(N) Zeit mit O(1) Zusatzspeicher.

Hinweise

Verwenden Sie die Zeiger prev, curr und next.
Speichern Sie curr->next, bevor Sie die Verknüpfung des aktuellen Knotens ändern.
Am Ende zeigt prev auf den neuen Listenkopf.

Quellcode

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

Im Compiler öffnen

Erklärung der Lösung

Setzen Sie prev auf NULL und curr auf den Kopf. Speichern Sie in jedem Schritt next, setzen Sie curr->next = prev und rücken Sie anschließend prev und curr weiter.

Verfolgen Sie eine Liste 1 → 2 → 3, um zu prüfen, dass der neue Kopf 3 und die letzte Verknüpfung NULL ist. Die ursprünglichen Knoten belegen O(N) Speicher, die Umkehrung ergänzt jedoch nur drei Zeiger.

Speichern Sie zum Freigeben der Liste die nächste Verknüpfung vor free. Greifen Sie nach der Freigabe nicht mehr auf den Knoten zu.

Lösungscode

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

Häufige Fragen

Warum bleiben Code und manche Ausgaben englisch?

C-Schlüsselwörter, Bezeichner, Programmkommentare und erwartete Ausgaben bleiben wie im Original, damit der Code ausführbar und die Tests konsistent bleiben. Erklärungen und Aufgabenstellungen sind übersetzt.