Nederlandse leereditie

Een enkelvoudig gekoppelde lijst omkeren in C

Verander koppelingen met drie pointers en geef de nieuwe lijstkop terug.

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

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) {
        // 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;
}

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.