ในบทความนี้ เราจำเป็นต้องย้อนกลับลิงก์โดยใช้รายการที่เชื่อมโยงเพียงอย่างเดียว งานของเราคือสร้างฟังก์ชันที่สามารถย้อนกลับรายการเชื่อมโยงที่กำหนดโดยลำพังได้ ตัวอย่างเช่น
Input: Following Linked list : 1->2->3->4->NULL Output: After processing of our function: 4->3->2->1->NULL
แนวทางในการหาทางออก
มีหลายวิธีในการย้อนกลับรายการที่เชื่อมโยง โดยทั่วไปแล้ว วิธีง่ายๆ ที่อยู่ในใจของเราคือการย้อนดูรายการและย้อนกลับในขณะที่ดำเนินการผ่าน
แนวทางง่ายๆ
เราจะตรวจสอบรายการที่เชื่อมโยงในแนวทางนี้และพยายามย้อนกลับในขณะที่ดำเนินการต่อไป
ตัวอย่าง
#include<bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
Node(int data) {
this->data = data;
next = NULL;
}
};
struct LinkedList {
Node* head;
LinkedList() { head = NULL; }
// Function to print linked list
void reverse() {
auto curr = head; // current pointer
Node* prev = NULL; // previous pointer
while(curr) {
auto temp = curr -> next;
curr -> next = prev;
prev = curr;
head = prev;
curr = temp;
}
}
void print() {
struct Node* temp = head;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
}
void push(int data) {
Node* temp = new Node(data);
temp->next = head;
head = temp;
}
};
int main() {
LinkedList list;
list.push(20);
list.push(4);
list.push(15);
list.push(85);
list.print();
list.reverse();
cout << "\n";
list.print();
} ผลลัพธ์
85 15 4 20 20 4 15 85
ในแนวทางนี้ เราเพียงแค่สำรวจรายการและย้อนกลับเมื่อเราดำเนินการผ่านรายการนั้น เป็นแนวทางที่ดีเนื่องจากความซับซ้อนของเวลาคือ O(N) โดยที่ N คือขนาดของรายการของเรา
ตอนนี้เราลองทำการทดลองหนึ่งที่เราพยายามใช้สแต็กเพื่อย้อนกลับรายการ
แนวทางกับ Stack
เราจะใช้สแต็กเพื่อเก็บโหนดทั้งหมดในโปรแกรมนี้และย้อนกลับโดยไปที่สแต็ก
ตัวอย่าง
#include<bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
Node(int data) {
this->data = data;
next = NULL;
}
};
struct LinkedList {
Node* head;
LinkedList() { head = NULL; }
// Function to print linked list
void reverse() {
auto curr = head; // current pointer
Node* prev = NULL; // previous pointer
stack<Node *> s;
while(curr) {
s.push(curr);
curr = curr -> next;
}
prev = s.top();
head = prev;
s.pop();
while(!s.empty()) {
auto temp = s.top();
s.pop();
prev -> next = temp;
prev = temp;
}
prev -> next = NULL;
}
void print() {
struct Node* temp = head;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
}
void push(int data) {
Node* temp = new Node(data);
temp->next = head;
head = temp;
}
};
int main() {
LinkedList list;
list.push(20);
list.push(4);
list.push(15);
list.push(85);
list.print();
list.reverse();
cout << "\n";
list.print();
}
ผลลัพธ์
85 15 4 20 20 4 15 85
คำอธิบายของโค้ดด้านบน
ในแนวทางนี้ เราจัดเก็บโหนดรายการในสแต็กในขณะที่กำลังดำเนินการ จากนั้นใช้สแต็กเพื่อป๊อปอัปและย้อนกลับรายการ วิธีการนี้ยังมีความซับซ้อนด้านเวลาของ O(N) โดยที่ N คือขนาดรายการของเรา ก่อนหน้านี้ เราใช้ stack ดังนั้นเราจึงสามารถใช้วิธีการแบบเรียกซ้ำได้เช่นเดียวกับที่ใช้สแต็ก ดังนั้นตอนนี้เราจะสร้างวิธีการแบบเรียกซ้ำ
แนวทางแบบเรียกซ้ำ
ในแนวทางนี้ เราจะทำขั้นตอนเดียวกันกับก่อนหน้านี้แต่มีการเรียกซ้ำ
ตัวอย่าง
#include<bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
Node(int data) {
this->data = data;
next = NULL;
}
};
struct LinkedList {
Node* head;
LinkedList() { head = NULL; }
// Function to print linked list
void rreverse(Node *curr, Node *prev) {
if(curr == NULL) {
// prev -> next = curr;
head = prev;
return;
}
rreverse(curr -> next, curr);
curr -> next = prev;
prev -> next = NULL;
}
void reverse() {
auto curr = head; // current pointer
Node* prev = NULL; // previous pointer
rreverse(curr -> next, curr);
}
void print() {
struct Node* temp = head;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
}
void push(int data) {
Node* temp = new Node(data);
temp->next = head;
head = temp;
}
};
int main() {
LinkedList list;
list.push(20);
list.push(4);
list.push(15);
list.push(85);
list.print();
list.reverse();
cout << "\n";
list.print();
} ผลลัพธ์
85 15 4 20 20 4 15 85
ในแนวทางนี้ เราทำแบบเดียวกันกับก่อนหน้านี้ แต่มีการโทรแบบเรียกซ้ำ ดังนั้นวิธีการนี้จึงมีความซับซ้อนด้านเวลาของ O(N) โดยที่ N คือขนาดของรายการของเรา
บทสรุป
ในบทความนี้ เราจะแก้ปัญหาการกลับรายการที่มีลิงก์อย่างเดียว นอกจากนี้เรายังได้เรียนรู้โปรแกรม C ++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ (ปกติและอีกสองวิธี) โดยที่เราแก้ไขปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ เราหวังว่าคุณจะพบว่าบทความนี้มีประโยชน์
