Edisi pembelajaran bahasa Indonesia. Kode dan keluarannya tetap seperti aslinya.

Pointer: membalik linked list

Balik tautan singly linked list dalam O(N) dan bebaskan seluruh node.

Bangun list berisi N integer menggunakan malloc. Implementasikan reverse_list yang mengubah tautan langsung dengan prev, curr, dan next. Kembalikan head baru, cetak nilai dalam urutan terbalik, dan bebaskan memori.

Jangan salin data ke array bantu. Setiap node harus dikunjungi sekali dan jumlah pointer tambahan tetap konstan. Periksa keberhasilan alokasi sebelum menulis.

Masukan

Baris pertama: N. Baris kedua: N integer yang dipisahkan spasi.

Keluaran

Satu baris berisi nilai list yang dibalik, dipisahkan spasi.

Batasan

1 <= N <= 100
-10000 <= nilai <= 10000
Waktu O(N) dan ruang tambahan O(1) untuk pembalikan.
Node dialokasikan dengan malloc dan semuanya dibebaskan.

Petunjuk

Simpan curr->next sebelum menimpa tautannya.
Saat selesai, curr bernilai NULL dan prev menunjuk head baru.

Kode C

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

Buka di kompiler

Solusi dan penjelasan

Mulai dengan prev = NULL dan curr = head. Pada setiap langkah, simpan next = curr->next, tetapkan curr->next = prev, lalu jalankan prev = curr dan curr = next.

Untuk list 1 → 2 → 3, hasil sementara adalah 1 → NULL, kemudian 2 → 1, lalu 3 → 2 → 1. Jangan kehilangan pointer ke bagian yang belum diproses.

Saat membebaskan memori, simpan node berikutnya sebelum free. Membaca node->next setelah free(node) tidak sah. Pembalikan memerlukan ruang tambahan O(1), sementara node asli tetap memakai O(N).

Kode solusi

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

Pertanyaan umum

Mengapa kode dan keluarannya tetap dalam bahasa Inggris?

Kata kunci, pengenal, dan teks yang diperiksa tes dipertahankan agar program tidak berubah. Penjelasan dan kontrol telah diterjemahkan.