Nhiệm vụ là in các nút bắt đầu từ cuối danh sách được liên kết mà không sử dụng thêm khoảng trắng, nghĩa là không được có thêm bất kỳ biến nào thay vào đó con trỏ tiêu đề trỏ đến nút đầu tiên sẽ được di chuyển.
Ví dụ
Input: 10 21 33 42 89 Output: 89 42 33 21 10
Có thể có nhiều giải pháp để in danh sách được liên kết theo thứ tự ngược lại, như cách tiếp cận đệ quy (sử dụng thêm không gian), đảo ngược danh sách được liên kết (yêu cầu sửa đổi trong Danh sách được liên kết đã cho), đẩy các phần tử lên một ngăn xếp rồi bật và hiển thị các phần tử từng cái một (yêu cầu khoảng trắng O (n)), nhưng những giải pháp này dường như sử dụng nhiều không gian hơn O (1).
Để đạt được kết quả mà không cần sử dụng nhiều hơn O (1), chúng tôi có thể -
- Đếm số lượng nút trong danh sách được liên kết
- Vòng lặp từ i =n đến 1 và in nút của vị trí thứ i.
Thuật toán
START Step 1 -> create node variable of type structure Declare int data Declare pointer of type node using *next Step 2 ->Declare function int get(struct node* head) Declare variable as int count=0 Declare struct node *newme=head Loop While newme!=NULL Increment count by 1 Set newme = newme->next End Return count Step 3 -> Declare Function void push(node** headref, char newdata) Allocate memory using malloc Set newnode->data = newdata Set newnode->next = (*headref) Set (*headref) = newnode Step 4 -> Declare function int getN(struct node* head, int n) Declare struct node* cur = head Loop for int i=0 and i<n-1 && cur != NULL and i++ Set cur=cur->next End Return cur->dataStep 5 -> Declare function void reverse(node *head) Declare int n = get(head) Loop For int i=n and i>=1 and i— Print getN(head,i) End Step 6 ->In Main() Create list using node* head = NULL Insert elements through push(&head, 89) Call reverse(head) STOP
Ví dụ
#include<stdio.h>
#include<stdlib.h>
//node structure
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* newme = head;
while (newme != NULL){
count++;
newme = newme->next;
}
return count;
}
int getN(struct node* head, int n) {
struct node* cur = head;
for (int i=0; i<n-1 && cur != NULL; 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; //create a first node
push(&head, 89); //pushing element in the list
push(&head, 42);
push(&head, 33);
push(&head, 21);
push(&head, 10);
reverse(head); //calling reverse function
return 0;
} Đầu ra
nếu chúng ta chạy chương trình trên thì nó sẽ tạo ra kết quả sau
89 42 33 21 10