Balikkan senarai terpaut menggunakan C++

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

Cara untuk mencari penyelesaian

Terdapat pelbagai cara untuk membalikkan senarai terpaut. Biasanya, kami memikirkan cara mudah untuk membalikkan senarai terpaut semasa melintasinya.

Kaedah Mudah

Dalam kaedah ini kita akan melintasi senarai pautan dan cuba membalikkannya semasa traversal.

Contoh

#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();
}

Output

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.

Kaedah menggunakan tindanan

Kami akan menggunakan tindanan untuk menyimpan semua nod dalam program ini dan membalikkannya dengan melintasi tindanan.

Contoh

#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();
}

Output

85 15 4 20
20 4 15 85

Penjelasan kod di atas

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.

Kaedah Rekursif

Dalam kaedah ini kita akan melakukan proses yang sama seperti sebelum ini tetapi menggunakan panggilan rekursif.

Contoh

#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();
}

Output

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.

Kesimpulan

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!