Program C untuk membalikkan senarai terpaut

Dalam soalan ini, kami diberi senarai pautan. Tugas kami ialah mencipta program untuk membalikkan senarai terpaut.

Program ini akan membalikkan senarai pautan yang diberikan dan mengembalikan senarai pautan terbalik.

Senarai terpaut ialah urutan terpaut yang mengandungi item. Setiap pautan mengandungi sambungan ke pautan lain.

Contoh

9 -> 32 -> 65 -> 10 -> 85 -> NULL

Senarai terpaut terbalik ialah membuat senarai terpaut dengan menterbalikkan pautan senarai terpaut. Nod kepala senarai terpaut akan menjadi nod terakhir senarai terpaut, dan nod terakhir akan menjadi nod kepala.

Contoh

Senarai terpaut terbalik terbentuk daripada senarai terpaut di atas −

85 -> 10 -> 65 -> 32 -> 9 -> NULL

Untuk membalikkan senarai terpaut yang diberikan, kami akan menggunakan tiga petunjuk tambahan untuk memproses. Penunjuk ini adalah sebelumnya, selepas dan semasa.

Kami pada mulanya akan menetapkan kedua-dua sebelumnya dan selepas kepada NULL, dan menetapkan semasa ke kepala senarai terpaut.

Selepas ini, kami mengulangi sehingga kami mencapai NULL senarai pautan awal. Kemudian lakukan perkara berikut:

after = current ->
next current ->
next = previous
previous = current
current = after

Sekarang mari buat program untuk membalikkan senarai terpaut. Terdapat dua cara untuk mencipta program ini, satu adalah berulang dan satu lagi adalah rekursif.

Program untuk menterbalikkan senarai terpaut (kaedah ekor-rekursif)

Contoh

Demonstrasi

#include <stdio.h>
struct Node {
   int data;
   struct Node* next;
};
Node* insertNode(int key) {
   Node* temp = new Node;
   temp->data = key;
   temp->next = NULL;
   return temp;
}
void tailRecRevese(Node* current, Node* previous, Node** head){
   if (!current->next) {
      *head = current;
      current->next = previous;
      return;
   }
   Node* next = current->next;
   current->next = previous;
   tailRecRevese(next, current, head);
}
void tailRecReveseLL(Node** head){
   if (!head)
      return;
   tailRecRevese(*head, NULL, head);
}
void printLinkedList(Node* head){
   while (head != NULL) {
      printf("%d ", head->data);
      head = head->next;
   }
   printf("</p><p>");
}
int main(){
   Node* head1 = insertNode(9);
   head1->next = insertNode(32);
   head1->next->next = insertNode(65);
   head1->next->next->next = insertNode(10);
   head1->next->next->next->next = insertNode(85);
   printf("Linked list : \t");
   printLinkedList(head1);
   tailRecReveseLL(&head1);
   printf("Reversed linked list : \t");
   printLinkedList(head1);
   return 0;
}

Output

Linked list : 9 32 65 10 85
Reversed linked list : 85 10 65 32 9

Program untuk menterbalikkan senarai kaedah terpaut)(Iterative method)

Demonstrasi masa nyata

#include <stdio.h>
struct Node {
   int data;
   struct Node* next;
   Node(int data){
      this->data = data;
      next = NULL;
   }
};
struct LinkedList {
   Node* head;
   LinkedList(){
      head = NULL;
   }
   void interReverseLL(){
      Node* current = head;
      Node *prev = NULL, *after = NULL;
      while (current != NULL) {
         after = current->next;
         current->next = prev;
         prev = current;
         current = after;
      }
      head = prev;
   }
   void print() {
      struct Node* temp = head;
      while (temp != NULL) {
         printf("%d ", temp-> data);
         temp = temp->next;
      }
      printf("</p><p>");
   }
   void push(int data){
      Node* temp = new Node(data);
      temp->next = head;
      head = temp;
   }
};
int main() {
   LinkedList linkedlist;
   linkedlist.push(85);
   linkedlist.push(10);
   linkedlist.push(65);
   linkedlist.push(32);
   linkedlist.push(9);
   printf("Linked List : \t");
   linkedlist.print();
   linkedlist.interReverseLL();
   printf("Reverse Linked List : \t");
   linkedlist.print();
   return 0;
}

Output

Linked List : 9 32 65 10 85
Reverse Linked List : 85 10 65 32 9

Atas ialah kandungan terperinci Program C untuk membalikkan senarai terpaut. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!