ในปัญหานี้ เราได้รับรายการเชื่อมโยง งานของเราคือสร้างโปรแกรมสำหรับย้อนกลับรายการที่เชื่อมโยง
โปรแกรมจะกลับรายการเชื่อมโยงที่กำหนดและส่งคืนรายการที่เชื่อมโยงกลับ
รายการที่เชื่อมโยง เป็นลำดับของลิงก์ที่มีรายการ แต่ละลิงก์มีการเชื่อมต่อกับลิงก์อื่น
ตัวอย่าง
9 -> 32 -> 65 -> 10 -> 85 -> NULL
เชื่อมโยงย้อนกลับ รายการเป็นรายการที่เชื่อมโยงที่สร้างขึ้นเพื่อสร้างรายการที่เชื่อมโยงโดยการย้อนกลับลิงก์ของรายการ โหนดหลักของรายการที่เชื่อมโยงจะเป็นโหนดสุดท้ายของรายการที่เชื่อมโยง และโหนดสุดท้ายจะเป็นโหนดหลัก
ตัวอย่าง
กลับรายการเชื่อมโยงที่เกิดขึ้นจากรายการที่เชื่อมโยงด้านบน -
85 -> 10 -> 65 -> 32 -> 9 -> NULL
ในการย้อนกลับรายการเชื่อมโยงที่กำหนด เราจะใช้ตัวชี้พิเศษสามตัวที่จะอยู่ในกระบวนการ ตัวชี้จะอยู่ก่อนหน้า หลัง ปัจจุบัน
เราจะเริ่มต้นก่อนหน้าและหลังเป็น NULL ในขั้นต้นและปัจจุบันไปยังส่วนหัวของรายการที่เชื่อมโยง
หลังจากนี้ เราจะทำซ้ำจนกว่าจะถึงค่า NULL ของรายการเริ่มต้น (รายการที่เชื่อมโยงแบบไม่ย้อนกลับ) และทำดังต่อไปนี้ −
after = current -> next current -> next = previous previous = current current = after
ตอนนี้ มาสร้างโปรแกรมสำหรับย้อนกลับรายการที่เชื่อมโยงกัน การสร้างโปรแกรมสามารถทำได้ 2 วิธี วิธีแรกเป็นแบบวนซ้ำและอีกวิธีหนึ่งเป็นแบบเรียกซ้ำ
โปรแกรมสำหรับย้อนกลับรายการที่เชื่อมโยง (วิธีการแบบเรียกซ้ำส่วนท้าย)
ตัวอย่าง
#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;
} ผลลัพธ์
Linked list : 9 32 65 10 85 Reversed linked list : 85 10 65 32 9
โปรแกรมสำหรับย้อนกลับรายการที่เชื่อมโยง (วิธีการวนซ้ำ)
ตัวอย่าง
#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;
} ผลลัพธ์
Linked List : 9 32 65 10 85 Reverse Linked List : 85 10 65 32 9
