In ngược danh sách liên kết không dùng bộ nhớ thêm và không sửa đổi trong C

In các nút của danh sách liên kết từ cuối về đầu không dùng bộ nhớ thêm (O(1) space) và không sửa đổi danh sách.

Ví dụ

Input: 10 -> 21 -> 33 -> 42 -> 89
Output: 89 42 33 21 10

Cách làm: Đếm số nút n, sau đó lặp i = n down to 1, in nút thứ i bằng cách duyệt từ head.

Thuật toán

BẮT ĐẦU
CẤU TRÚC node {data, next}
HÀM get(head) -> ĐẾM SỐ NÚT
HÀM push(headref, data) -> THÊM ĐẦU
HÀM getN(head, n) -> TRẢ VỀ DATA NÚT THỨ n
HÀM reverse(head)
    n = get(head)
    VỚI i = n ĐẾN 1: IN getN(head, i)
KẾT THÚC

Chương trình C ví dụ

#include <stdio.h>
#include <stdlib.h>

struct node { int data; struct node* next; };

void push(struct node** headref, int newdata) {
    struct node* newnode = (struct node*)malloc(sizeof(struct node));
    newnode->data = newdata;
    newnode->next = *headref;
    *headref = newnode;
}

int get(struct node* head) {
    int count = 0;
    struct node* cur = head;
    while (cur) { count++; cur = cur->next; }
    return count;
}

int getN(struct node* head, int n) {
    struct node* cur = head;
    for (int i = 0; i < n-1 && cur; i++) cur = cur->next;
    return cur->data;
}

void reverse(node* head) {
    int n = get(head);
    for (int i = n; i >= 1; i--)
        printf("%d ", getN(head, i));
}

int main() {
    struct node* head = NULL;
    push(&head, 89); push(&head, 42); push(&head, 33);
    push(&head, 21); push(&head, 10);
    reverse(head);
    return 0;
}

Kết quả

89 42 33 21 10