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

Membalik linked list dalam C

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

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

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.