ในปัญหานี้ เราได้รับ Linked List มาหนึ่งรายการ งานของเราคือการสร้างโปรแกรมเพื่อย้อนกลับ Linked List นั้น
โปรแกรมจะทำการย้อนกลับ Linked List ที่กำหนดและคืนค่า Linked List ที่ย้อนกลับแล้ว
Linked List คือลำดับของลิงก์ที่มีรายการอยู่แต่ละลิงก์มีการเชื่อมต่อไปยังลิงก์ถัดไป
ตัวอย่าง
9 → 32 → 65 → 10 → 85 → NULL
Linked List ที่ย้อนกลับ คือ Linked List ที่สร้างขึ้นโดยการย้อนกลับลิงก์ของรายการเดิม โหนดหัว (head) ของ Linked List เดิมจะกลายเป็นโหนดสุดท้าย และโหนดสุดท้ายจะกลายเป็นโหนดหัวใหม่
ตัวอย่าง
Linked List ที่ย้อนกลับจาก Linked List ด้านบนคือ
85 → 10 → 65 → 32 → 9 → NULL
เพื่อย้อนกลับ Linked List ที่กำหนด เราจะใช้ตัวชี้ (pointer) เพิ่มเติม 3 ตัวในกระบวนการ ได้แก่ previous, after, current
เราจะกำหนดค่าเริ่มต้นให้ previous และ after เป็น NULL และ current เป็น head ของ Linked List
หลังจากนั้น เราจะวนลูปจนกว่าจะถึง NULL ของ Linked List เดิม (ที่ยังไม่ได้ย้อนกลับ) และทำดังนี้
after = current → next current → next = previous previous = current current = after
ตอนนี้มาสร้างโปรแกรมสำหรับการย้อนกลับ Linked List กัน มี 2 วิธีคือ วิธีวนซ้ำ (Iterative) และวิธีเรียกซ้ำ (Recursive)
โปรแกรมย้อนกลับ Linked List (วิธี Tail-Recursive)
ตัวอย่าง
#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
โปรแกรมย้อนกลับ Linked List (วิธี Iterative)
ตัวอย่าง
#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
