Trong vấn đề này, chúng tôi được cung cấp một danh sách liên kết. Nhiệm vụ của chúng tôi là tạo một chương trình để đảo ngược danh sách được liên kết.
Chương trình sẽ đảo ngược danh sách liên kết đã cho và trả về danh sách liên kết đã đảo ngược.
Danh sách được liên kết là một chuỗi các liên kết với các mục chứa. Mỗi liên kết chứa một kết nối đến một liên kết khác.
Ví dụ
9 -> 32 -> 65 -> 10 -> 85 -> NULL
Liên kết ngược list là một danh sách liên kết được tạo để tạo thành một danh sách liên kết bằng cách đảo ngược các liên kết của danh sách. Nút đầu của danh sách được liên kết sẽ là nút cuối cùng của danh sách được liên kết và nút cuối cùng sẽ là nút đầu.
Ví dụ
Danh sách liên kết ngược được hình thành từ danh sách liên kết ở trên -
85 -> 10 -> 65 -> 32 -> 9 -> NULL
Để đảo ngược danh sách liên kết đã cho, chúng tôi sẽ sử dụng ba con trỏ bổ sung sẽ có trong quá trình này. Các con trỏ sẽ là trước, sau, hiện tại.
Chúng tôi sẽ khởi tạo trước và sau thành NULL ban đầu và hiện tại ở đầu danh sách được liên kết.
Sau đó, chúng tôi sẽ lặp lại cho đến khi chúng tôi đạt đến NULL của danh sách ban đầu (danh sách liên kết không đảo ngược). Và làm như sau -
after = current -> next current -> next = previous previous = current current = after
Bây giờ chúng ta hãy tạo một chương trình để đảo ngược danh sách được liên kết. Có thể có hai cách để tạo chương trình, một là lặp đi lặp lại và một là đệ quy.
Chương trình đảo ngược danh sách được liên kết (phương pháp đệ quy đuôi)
Ví dụ
#include <stdio.h>
struct Node {
int data;
struct Node* next;
};
Node* insertNode(int key) {
Node* temp = new Node;
temp->data = key;
temp->next = NULL;
return temp;
}
void tailRecRevese(Node* current, Node* previous, Node** head){
if (!current->next) {
*head = current;
current->next = previous;
return;
}
Node* next = current->next;
current->next = previous;
tailRecRevese(next, current, head);
}
void tailRecReveseLL(Node** head){
if (!head)
return;
tailRecRevese(*head, NULL, head);
}
void printLinkedList(Node* head){
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}
int main(){
Node* head1 = insertNode(9);
head1->next = insertNode(32);
head1->next->next = insertNode(65);
head1->next->next->next = insertNode(10);
head1->next->next->next->next = insertNode(85);
printf("Linked list : \t");
printLinkedList(head1);
tailRecReveseLL(&head1);
printf("Reversed linked list : \t");
printLinkedList(head1);
return 0;
} Đầu ra
Linked list : 9 32 65 10 85 Reversed linked list : 85 10 65 32 9
Chương trình đảo ngược danh sách được liên kết (phương pháp lặp lại)
Ví dụ
#include <stdio.h>
struct Node {
int data;
struct Node* next;
Node(int data){
this->data = data;
next = NULL;
}
};
struct LinkedList {
Node* head;
LinkedList(){
head = NULL;
}
void interReverseLL(){
Node* current = head;
Node *prev = NULL, *after = NULL;
while (current != NULL) {
after = current->next;
current->next = prev;
prev = current;
current = after;
}
head = prev;
}
void print() {
struct Node* temp = head;
while (temp != NULL) {
printf("%d ", temp-> data);
temp = temp->next;
}
printf("\n");
}
void push(int data){
Node* temp = new Node(data);
temp->next = head;
head = temp;
}
};
int main() {
LinkedList linkedlist;
linkedlist.push(85);
linkedlist.push(10);
linkedlist.push(65);
linkedlist.push(32);
linkedlist.push(9);
printf("Linked List : \t");
linkedlist.print();
linkedlist.interReverseLL();
printf("Reverse Linked List : \t");
linkedlist.print();
return 0;
} Đầu ra
Linked List : 9 32 65 10 85 Reverse Linked List : 85 10 65 32 9