Deutsche Lernausgabe

C-Zeiger: Eine verkettete Liste umkehren

Kehren Sie die Verknüpfungen einer einfach verketteten Liste um und geben Sie ihre Knoten korrekt frei.

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
struct Node* reverse_list(struct Node *head) {
    // TODO: Implement 3-pointer iterative reversal
    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);

    // Print list
    struct Node *curr = head;
    while (curr != NULL) {
        printf("%d%c", curr->data, curr->next == NULL ? '\n' : ' ');
        curr = curr->next;
    }

    // Free memory
    curr = head;
    while (curr != NULL) {
        struct Node *temp = curr->next;
        free(curr);
        curr = temp;
    }

    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) {
        next = curr->next; // Store next node pointer
        curr->next = prev; // Reverse current node's pointer backwards
        prev = curr;       // Advance prev pointer to current
        curr = next;       // Advance current pointer to next
    }

    return prev; // 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;
        if (scanf("%d", &val) != 1) return 1;
        struct Node *new_node = (struct Node *)malloc(sizeof(struct Node));
        if (new_node == NULL) return 1;
        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%c", curr->data, curr->next == NULL ? '\n' : ' ');
        curr = curr->next;
    }

    // Clean up heap allocations
    curr = head;
    while (curr != NULL) {
        struct Node *temp = curr->next;
        free(curr);
        curr = temp;
    }

    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.