इस लेख में, हमें एक सिंगली लिंक्ड लिस्ट की मदद से लिंक्स को उल्टा करना है। हमारा कार्य एक ऐसा फंक्शन बनाना है जो दी गई सिंगली लिंक्ड लिस्ट को उल्टा करने में सक्षम हो। उदाहरण के लिए
इनपुट: निम्न लिंक्ड लिस्ट: 1→2→3→4→NULL आउटपुट: हमारे फंक्शन के प्रसंस्करण के बाद: 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; } // लिंक्ड लिस्ट प्रिंट करने का फंक्शन void reverse() { auto curr = head; // वर्तमान पॉइंटर Node* prev = NULL; // पिछला पॉइंटर 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; } // लिंक्ड लिस्ट प्रिंट करने का फंक्शन void reverse() { auto curr = head; // वर्तमान पॉइंटर Node* prev = NULL; // पिछला पॉइंटर 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 हमारी लिस्ट का आकार है। चूंकि हम पहले स्टैक का उपयोग कर रहे थे, इसलिए हम एक रिकर्सिव दृष्टिकोण का भी उपयोग कर सकते हैं क्योंकि वह भी स्टैक का उपयोग करता है, तो अब हम एक रिकर्सिव दृष्टिकोण बनाएंगे।
रिकर्सिव दृष्टिकोण
इस दृष्टिकोण में, हम पहले जैसी ही प्रक्रिया करेंगे लेकिन रिकर्सिव कॉल के साथ।
उदाहरण
#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; } // लिंक्ड लिस्ट प्रिंट करने का फंक्शन 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; // वर्तमान पॉइंटर Node* prev = NULL; // पिछला पॉइंटर 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, जावा, पायथन और अन्य भाषाओं में भी वही प्रोग्राम लिख सकते हैं। हमें उम्मीद है कि आपको यह लेख उपयोगी लगा होगा।
