Nhiệm vụ là in phần ngược lại của một danh sách liên kết đã cho bằng cách sử dụng hàm đệ quy. Chương trình phải in ngược nhưng không đảo ngược danh sách nghĩa là thứ tự của các nút vẫn giữ nguyên
Tại đây, chương trình sẽ di chuyển con trỏ đầu chứa địa chỉ của nút đầu tiên đến nút tiếp theo cho đến khi kiểm tra NULL được lưu trong nút cuối cùng của danh sách và in ra dữ liệu của nút đầu.
Ví dụ
Input: 29 34 43 56 Output: 56 43 34 29
Đầu tiên, các nút được chèn vào danh sách và một con trỏ sẽ bắt đầu trỏ đến các nút được chèn. Sau khi danh sách cuối cùng được tạo, giả sử con trỏ tạm thời sẽ được khởi tạo với con trỏ nút đầu tiên và nó tiếp tục tăng cho đến khi địa chỉ tiếp theo của nút là NULL vì nút cuối cùng trỏ đến không và từ nút cuối cùng, danh sách được duyệt cho đến con trỏ đầu. Nó sẽ hiển thị đảo ngược danh sách mà không thực sự đảo ngược danh sách.
Đoạn mã dưới đây cho thấy cách triển khai c của thuật toán đã cho.
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 void reverse(node* head) IF head == NULL return Call reverse(head->next) Print head->data Step 3 -> Declare Function void push(node** header, char newdata) Allocate memory using malloc Set newnode->data = newdata Set newnode->next = (*header) Set (*header) = newnode Step 4 ->In Main() Create list using node* head = NULL Insert elements through push(&head, 56) Call reverse(head) STOP
Ví dụ
#include<stdio.h>
#include<stdlib.h>
//creating structure for a node
struct node {
int data;
node* next;
};
//function to print reverse of the data in the list
void reverse(node* head) {
if (head == NULL)
return;
reverse(head->next);
printf("%d ", head->data);
}
//function to puch the node in the list
void push(node** header, char newdata) {
struct node* newnode = (struct node*)malloc(sizeof(struct node));
newnode->data = newdata;
newnode->next = (*header);
(*header) = newnode;
}
int main() {
node* head = NULL;
push(&head, 56); //calling function to push 56 in the list
push(&head, 43);
push(&head, 34);
push(&head, 29);
reverse(head);
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.
reverse of a linked list 56 43 34 29