Dalam artikel ini, kita perlu membalikkan pautan dengan bantuan senarai pautan tunggal. Tugas kami adalah untuk mencipta fungsi yang boleh membalikkan senarai pautan tunggal yang diberikan. Contohnya
Input: Following Linked list : 1->2->3->4->NULL Output: After processing of our function: 4->3->2->1->NULL
Terdapat pelbagai cara untuk membalikkan senarai terpaut. Biasanya, kami memikirkan cara mudah untuk membalikkan senarai terpaut semasa melintasinya.
Dalam kaedah ini kita akan melintasi senarai pautan dan cuba membalikkannya semasa traversal.
#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
Dalam pendekatan ini kita hanya melelang melalui senarai dan membalikkannya semasa lelaran. Ini adalah pendekatan yang baik kerana kerumitan masa ialah O(N), dengan N ialah saiz senarai kami.
Kini kami cuba melakukan eksperimen dan cuba membalikkan senarai menggunakan tindanan.
Kami akan menggunakan tindanan untuk menyimpan semua nod dalam program ini dan membalikkannya dengan melintasi tindanan.
#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
Dalam pendekatan ini, kami menyimpan nod senarai dalam timbunan semasa merentasi senarai dan kemudian menggunakan timbunan untuk meletuskannya dan membalikkan tujuan ini pendekatan Kerumitan masa juga O(N), di mana N ialah saiz senarai kami. Seperti sebelum ini, kami menggunakan timbunan, jadi kami juga boleh menggunakan kaedah rekursif, kerana rekursi juga menggunakan timbunan, dan sekarang kami akan menggunakan kaedah rekursif.
Dalam kaedah ini kita akan melakukan proses yang sama seperti sebelum ini tetapi menggunakan panggilan rekursif.
#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
Dalam pendekatan ini kami melakukan perkara yang sama seperti sebelumnya tetapi menggunakan panggilan rekursif jadi kerumitan masa pendekatan ini juga O(N) di mana N ialah saiz senarai kami.
Dalam artikel ini, kami menyelesaikan masalah menyongsangkan senarai pautan tunggal. Kami juga mempelajari program C++ dan kaedah lengkap (kaedah biasa dan dua kaedah lain) untuk menyelesaikan masalah ini. Kita boleh menulis program yang sama dalam bahasa lain seperti C, Java, Python dan lain-lain. Semoga artikel ini membantu anda.
Atas ialah kandungan terperinci Balikkan senarai terpaut menggunakan C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!