Nederlandse leereditie

C-pointers: een lijst omkeren

Keer de koppelingen van een enkelvoudige lijst om en geef knopen correct vrij.

Bouw een lijst uit de ingelezen waarden. reverse_list moet de koppelingen van bestaande knopen omkeren en de nieuwe kop teruggeven zonder een tweede lijst te maken.

Geef na de uitvoer alle knopen vrij. Controleer elke malloc: mislukking mag niet leiden tot derefereren van NULL of verlies van al gereserveerde knopen.

Invoer

N, daarna N gehele getallen in de oorspronkelijke lijstvolgorde.

Uitvoer

Waarden van de omgekeerde lijst op één regel, gescheiden door spaties.

Voorwaarden

1 ≤ N ≤ 100; waarden van -10000 tot 10000.
Omkeren in O(N) tijd en O(1) extra geheugen.

Hints

Houd de pointers prev, curr en next bij.
Bewaar curr->next voordat je de huidige koppeling wijzigt.
Aan het einde wijst prev naar de nieuwe kop.

Broncode

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

Openen in de compiler

Uitleg van de oplossing

Initialiseer prev op NULL en curr op de kop. Bewaar per stap next, zet curr->next = prev en verplaats daarna prev en curr.

Volg 1 → 2 → 3: de nieuwe kop moet 3 zijn en de laatste koppeling NULL. De knopen gebruiken O(N) geheugen, maar de omkering voegt slechts drie pointers toe.

Bewaar bij vrijgeven de volgende koppeling vóór free. Benader de vrijgegeven knoop niet meer.

Oplossingscode

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

Veelgestelde vragen

Waarom blijven code en sommige resultaten Engels?

C-sleutelwoorden, namen, programmacommentaar en verwachte uitvoer blijven gelijk aan het origineel om uitvoerbare code en consistente tests te behouden. Uitleg en instructies zijn vertaald.