Trong bài viết này, chúng ta cần đảo ngược các liên kết với sự trợ giúp của một danh sách được liên kết đơn lẻ. Nhiệm vụ của chúng ta là tạo một hàm có khả năng đảo ngược danh sách liên kết đơn đã cho. Ví dụ
Input: Following Linked list : 1->2->3->4->NULL Output: After processing of our function: 4->3->2->1->NULL
Phương pháp tiếp cận để tìm ra giải pháp
Có nhiều cách tiếp cận khác nhau để đảo ngược danh sách được liên kết. Nói chung, chúng ta nghĩ đến một cách tiếp cận đơn giản để xem qua danh sách và đảo ngược danh sách trong khi xem qua.
Cách tiếp cận đơn giản
Chúng tôi sẽ xem qua danh sách được liên kết trong cách tiếp cận này và cố gắng đảo ngược nó trong khi xem qua nó.
Ví dụ
#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();
} Đầu ra
85 15 4 20 20 4 15 85
Trong cách tiếp cận này, chúng ta chỉ đơn giản là lướt qua danh sách và đảo ngược khi chúng ta lướt qua nó. Đó là một cách tiếp cận tốt vì độ phức tạp về thời gian là O (N) , trong đó N là kích thước của danh sách của chúng tôi.
Bây giờ chúng tôi cố gắng thực hiện một thử nghiệm trong đó chúng tôi cố gắng sử dụng ngăn xếp để đảo ngược danh sách.
Phương pháp tiếp cận với ngăn xếp
Chúng tôi sẽ sử dụng một ngăn xếp để lưu trữ tất cả các nút trong chương trình này và đảo ngược chúng bằng cách đi qua ngăn xếp.
Ví dụ
#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();
}
Đầu ra
85 15 4 20 20 4 15 85
Giải thích về Quy tắc trên
Trong cách tiếp cận này, chúng tôi lưu trữ các nút danh sách trong một ngăn xếp trong khi đi qua nó và sau đó sử dụng ngăn xếp để bật chúng và đảo ngược danh sách; Cách tiếp cận này cũng có độ phức tạp về thời gian là O (N), trong đó N là kích thước danh sách của chúng ta. Như trước đó, chúng tôi đã sử dụng ngăn xếp, vì vậy chúng tôi cũng có thể sử dụng một cách tiếp cận đệ quy vì cách tiếp cận đó cũng sử dụng ngăn xếp, vì vậy bây giờ chúng tôi sẽ thực hiện một cách tiếp cận đệ quy.
Phương pháp tiếp cận đệ quy
Trong cách tiếp cận này, chúng ta sẽ thực hiện quy trình tương tự như trước đó nhưng với các cuộc gọi đệ quy.
Ví dụ
#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();
} Đầu ra
85 15 4 20 20 4 15 85
Trong cách tiếp cận này, chúng tôi đang thực hiện tương tự như trước đó, nhưng với lời gọi đệ quy, do đó, cách tiếp cận này cũng có độ phức tạp về thời gian là O (N) , trong đó N là kích thước của danh sách của chúng tôi.
Kết luận
Trong bài viết này, chúng tôi giải quyết vấn đề Đảo ngược một danh sách được liên kết đơn lẻ. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường và hai cách tiếp cận khác) mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Chúng tôi hy vọng bạn thấy bài viết này hữu ích.