सी प्रोग्राम फॉर रिवर्स ए लिंक्ड लिस्ट

इस समस्या में हमें एक लिंक्ड लिस्ट दी जाती है। हमारा काम एक लिंक की गई सूची को उलटने के लिए एक प्रोग्राम बनाना है।

प्रोग्राम दी गई लिंक की गई सूची को उलट देगा और उलटी लिंक की गई सूची को वापस कर देगा।

लिंक की गई सूची लिंक का एक क्रम है जिसमें आइटम शामिल हैं। प्रत्येक लिंक में दूसरे लिंक से कनेक्शन होता है।

उदाहरण

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

रिवर्स लिंक किया गया सूची एक लिंक की गई सूची है जो सूची के लिंक को उलट कर एक लिंक की गई सूची बनाने के लिए बनाई गई है। लिंक्ड लिस्ट का हेड नोड लिंक्ड लिस्ट का आखिरी नोड होगा और आखिरी वाला हेड नोड होगा।

उदाहरण

उपरोक्त लिंक की गई सूची से बनी रिवर्स लिंक्ड सूची -

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

दी गई लिंक्ड सूची को उलटने के लिए हम तीन अतिरिक्त पॉइंटर्स का उपयोग करेंगे जो प्रक्रिया में होंगे। पॉइंटर्स पिछले, बाद में, वर्तमान होंगे।

हम पहले और बाद में NULL को प्रारंभ में और वर्तमान को लिंक की गई सूची के शीर्ष पर प्रारंभ करेंगे।

इसके बाद, हम तब तक पुनरावृति करेंगे जब तक हम प्रारंभिक (नॉन-रिवर्स लिंक्ड लिस्ट) के NULL तक नहीं पहुंच जाते। और निम्न कार्य करें -

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

अब लिंक की गई सूची को उलटने के लिए एक प्रोग्राम बनाते हैं। प्रोग्राम बनाने के दो तरीके हो सकते हैं, एक पुनरावृत्त है और दूसरा पुनरावर्ती है।

लिंक की गई सूची को उलटने का कार्यक्रम (पूंछ-पुनरावर्ती दृष्टिकोण)

उदाहरण

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

आउटपुट

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

लिंक की गई सूची को उलटने का कार्यक्रम (पुनरावृत्त दृष्टिकोण)

उदाहरण

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

आउटपुट

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