इस लेख में, हमें सिंगल लिंक्ड लिस्ट की मदद से लिंक्स को उलटने की जरूरत है। हमारा काम एक ऐसा फंक्शन बनाना है जो दी गई सिंगल लिंक्ड लिस्ट को उलटने में सक्षम हो। उदाहरण के लिए
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 हमारी सूची का आकार है।
अब हम एक प्रयोग करने का प्रयास करते हैं जहां हम सूची को उलटने के लिए स्टैक का उपयोग करने का प्रयास करते हैं।
स्टैक के साथ दृष्टिकोण
हम इस प्रोग्राम में सभी नोड्स को स्टोर करने के लिए एक स्टैक का उपयोग करेंगे और स्टैक के माध्यम से उन्हें उलट देंगे।
उदाहरण
#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
उपरोक्त कोड की व्याख्या
इस दृष्टिकोण में, हम सूची नोड्स को इसके माध्यम से जाने के दौरान एक स्टैक में संग्रहीत करते हैं और फिर उन्हें पॉप करने और सूची को उलटने के लिए स्टैक का उपयोग करते हैं; इस दृष्टिकोण में ओ (एन) की समय जटिलता भी है, जहां एन हमारी सूची का आकार है। पहले की तरह, हम स्टैक का उपयोग कर रहे थे, इसलिए हम एक पुनरावर्ती दृष्टिकोण का भी उपयोग कर सकते हैं क्योंकि वह भी स्टैक का उपयोग करता है, इसलिए अब हम एक पुनरावर्ती दृष्टिकोण बनाएंगे।
पुनरावर्ती दृष्टिकोण
इस दृष्टिकोण में, हम पहले की तरह ही प्रक्रिया करेंगे लेकिन पुनरावर्ती कॉल के साथ।
उदाहरण
#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++ प्रोग्राम और संपूर्ण दृष्टिकोण (सामान्य और दो अन्य दृष्टिकोण) भी सीखा जिसके द्वारा हमने इस समस्या को हल किया। हम उसी प्रोग्राम को अन्य भाषाओं जैसे सी, जावा, पायथन और अन्य भाषाओं में लिख सकते हैं। हमें उम्मीद है कि आपको यह लेख मददगार लगा होगा।